C++ Easy Toposort Solution || Clean Code || Explained with comments
The main intuition behind the approach is that, we can find the ancestor of a node only if we know the parents of the current node. We start from the node havin
***The main intuition behind the approach is that, we can find the ancestor of a node only if we know the parents of the current node. We start from the node having no parent so that the ancestor of the node is also empty, then the children of that node will have their parent and the parent of parent and this will go so on***\n\n***This gives the clue that, we need to first analyse the parent of the node and then we need to analyse the node, so we thought of using toposort, the toposort works in such a manner that, the parent of current node will have occured before the current node. Means while finding the ancestor of the current node, we must have found the ancestor of its parent node, hence we will put the parent into the ancestor of current node and the ancestor array of its parents in the current node answer***\n\n```\nclass Solution {\npublic:\n    \n    //here we are finding the toposort \n    void findtoposort(int node, vector<int>&vis, unordered_map<int,vector<int>>&adj, stack<int>&stk){\n        vis[node] = 1;\n        \n        for(int x: adj[node]){\n            if(!vis[x]){\n                findtoposort(x, vis, adj,stk);\n            }\n        }\n        \n        stk.push(node);\n    }\n    \n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        //this is the ancestor ans which we need to return \n        vector<vector<int>>ans(n);\n        //here is the visited array for finding the toposort\n        vector<int>vis(n,0);\n        //here is the stack for containing the elements of the DAG in topological sort manner\n        stack<int>stk;\n        \n        //here we have created adjancency list in the mapped form as the node and then its children\n        unordered_map<int, vector<int>>adj;\n        //inserting children into the adjencency list\n        for(int i = 0; i<edges.size(); i++){\n            adj[edges[i][0]].push_back(edges[i][1]);\n        }\n        \n        //here we are finding the toposort of the elements of the graph\n        for(int i = 0; i<n; i++){\n            if(!vis[i]){\n                findtoposort(i, vis, adj, stk);\n            }\n        }\n        \n        //here is the map to store the parents of a node\n        //first is the node and second is the set containing all the parents of the current node\n        unordered_map<int, set<int>>mp;\n        //inserting parents into the node\n        for(int i = 0; i<edges.size(); i++){\n            mp[edges[i][1]].insert(edges[i][0]);\n        }\n        \n        //here we are traversing the stack in topological sort manner so that answer can be evaluated\n        while(stk.empty()==false){\n            int currnode = stk.top();\n            stk.pop();\n            set<int>s;\n            \n            for(int x: mp[currnode]){\n                s.insert(x);\n                s.insert(ans[x].begin(), ans[x].end());\n            }\n            \n            vector<int>currvec(s.begin(), s.end());\n            ans[currnode] = currvec;\n        }\n        \n        return ans;\n    }\n};\n```
['Topological Sort', 'C', 'C++']