leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1519.cpp (1095B)

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