C++ | Topological sort | Brief explanation | Similar to Course Schedule Problem
Intuition\n1. Since the graph is DAG and we need to find all the ancestors of a node. (Its kinda similar to Course Schedule Problem where we need to satisfy all
**Intuition**\n1. Since the graph is DAG and we need to find all the ancestors of a node. (Its kinda similar to Course Schedule Problem where we need to satisfy all prerequisite courses to do a particular course)\n2. Topological sort came to my mind.\n3. The concept is exactly same but we have to do some little tweaks. \n4. For the current node all the neighbours we can reach will contain the current node as ancestor and all the ancestor of the current node will also be the ancestors of neighbours we can reach from current node. \n5. So we will just iterate thru current node\'s ancestor and push it inside neighbour\'s ancestor vector and also push the current node because this would be an immediate and original predecessor.\n6. also maintain a set for each node for storing ancestors because we can visit or add same node multiple times for a neighbour.\n7. DONE!!!!!\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        int sz = edges.size();\n        vector<vector<int>> l(n);\n        vector<int> indegree(n,0);   \n        \n        vector<set<int>> ans(n);\n\n        for(int i = 0;i<sz;i++){\n            l[edges[i][0]].push_back(edges[i][1]);\n            indegree[edges[i][1]]++;   \n        }\n        \n        queue<int> topological_order;\n        \n        for(int i = 0;i<n;i++){\n            if(indegree[i] == 0){  \n                topological_order.push(i);\n                ans[i] = {};   \n            }\n        }\n        \n            \n        while(!topological_order.empty()){\n            int node = topological_order.front();\n\n            topological_order.pop();\n            for(auto nbr : l[node]){\n                    indegree[nbr]--;\n                if(indegree[nbr] == 0){\n                    topological_order.push(nbr);\n                }\n\n                    for(auto x : ans[node]){\n                        ans[nbr].insert(x);\n                    }\n                    ans[nbr].insert(node);\n\n                }\n            }\n            \n        vector<vector<int>> res(n);\n        \n        for(int i = 0;i<ans.size();i++){\n            for(auto x : ans[i]){\n                res[i].push_back(x);\n            }\n        }\n        \n        return res;\n    }\n};\n```
['Topological Sort', 'C']