leetcode

Solution to some Leetcode problems written in C++

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

2192.cpp (719B)

0 class Solution { 1 public: 2 vector<vector<int>> getAncestors(int n, vector<vector<int>> &edges) { 3 vector<vector<int>> adj(n, vector<int>()); 4 vector<vector<int>> anc(n, vector<int>()); 5 6 for (auto &p : edges) 7 adj[p[0]].push_back(p[1]); 8 for (int i = 0; i < n; i++) { 9 stack<int> st; 10 st.push(i); 11 while (!st.empty()) { 12 int root = st.top(); 13 st.pop(); 14 for (int c : adj[root]) { 15 if (!anc[c].empty() && anc[c].back() == i) continue; 16 anc[c].push_back(i); 17 st.push(c); 18 } 19 } 20 } 21 22 return anc; 23 } 24 };