leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1519.cpp (1095B)

      1 class Solution {
      2   public:
      3     vector<int> countSubTrees(int n, vector<vector<int>> &edges, string labels) {
      4         vector<vector<int>> adj(n, vector<int>()), count(n, vector<int>(26, 0));
      5         vector<bool> visited(n, false);
      6         vector<int> res(n);
      7 
      8         for (auto &e : edges) {
      9             adj[e[0]].push_back(e[1]);
     10             adj[e[1]].push_back(e[0]);
     11         }
     12 
     13         stack<int> st;
     14         st.push(0);
     15         while (!st.empty()) {
     16             int crnt = st.top();
     17             if (visited[crnt]) {
     18                 st.pop();
     19 
     20                 for (int c : adj[crnt]) {
     21                     if (visited[c]) continue;
     22                     for (int i = 0; i < 26; i++)
     23                         count[crnt][i] += count[c][i];
     24                 }
     25                 res[crnt] = ++count[crnt][labels[crnt] - 'a'];
     26                 visited[crnt] = false;
     27                 continue;
     28             }
     29 
     30             visited[crnt] = true;
     31             for (int c : adj[crnt]) {
     32                 if (visited[c]) continue;
     33                 st.push(c);
     34             }
     35         }
     36 
     37         return res;
     38     }
     39 };