leetcode

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

2192.cpp (719B)

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