C++ BFS-Kahn's Algorithm ||Explained with Image and Dry Run|| Topological Sort
\n\n\nn = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]\n\nNow adjancecy list will be:\n0 -> 1,2,3,4\n1 -> 2,3,4\n2 -> 3,4\n3 -> 4
\n![image](https://assets.leetcode.com/users/images/2a09ff9f-1953-4502-aca9-db7e2b285cdc_1646514461.6325643.png)\n\n**n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]**\n\nNow **adjancecy list** will be:\n0 -> 1,2,3,4\n1 -> 2,3,4\n2 -> 3,4\n3 -> 4\n4 ->\n\n**Indegree vector:**\n0 -> 0\n1 -> 1\n2 -> 2\n3 -> 3\n4 -> 4\n\nSo queue will have just 0 while starting\n**cur=0**\n\nso **\'it\'** will have the value **1,2,3,4** one by one\nand st[it].insert(cur) will make the set look like\n**0 -> \n1 -> 0\n2 -> 0\n3 -> 0\n4 -> 0**\n\nAfter **indegree[it]--**\n**indegree array** will look like\n0 -> 0\n1 -> 0\n2 -> 1\n3 -> 2\n4 -> 3\n\ntherefore 1 willl be pushed into the queue\n\nnow for next iteration **cur=1**\n\nso \'it\' will have the value 2,3,4 one by one\nand **st[it].insert(cur)** will make the set look like\n0 -> \n1 -> 0\n2 -> 0,1\n3 -> 0,1\n4 -> 0,1\n\nnow \nfor(auto it2:st[cur])\n     st[it].insert(it2);\n\t \nThis will add parent of 1(ancestors of \'it\') in all the childnode of cur i.e 1\nAlthough in this case, 0 is the direct parent of 2,3,4 so 0 is already present.\n\n**BUT\nin a scenario where  ADJ LIST is\n0 -> 1\n1 -> 2,3,4\n2 -> 3,4\n3 -> 4\n4 ->\nthen \nfor 2,3,4  0 would have also been added as an ancestor by the above 2 lines of code.**\n\nMoving on\nAfter indegree[it]--\nindegree array will look like\n0 -> 0\n1 -> 0\n2 -> 0\n3 -> 1\n4 -> 2\n\n**therefore 2 willl be pushed into the queue\nand iteration continues**\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        //stores vector of adjacency list with each node having a vector of nodes to which it points \n        vector<int> adj_list[n];   \n        \n        //stores indegree of each node\n        vector<int> indegree(n);\n        \n        //creating adjacency list and updating indegrees\n        for(int i=0;i<edges.size();++i)\n        {\n            adj_list[edges[i][0]].push_back(edges[i][1]);\n            indegree[edges[i][1]]++;\n        }\n        \n        //queue for BFS Traversal\n        queue<int> q; \n        \n        //adding all the nodes with indegree==0 as they act as the source node\n        for(int i=0;i<n;++i)\n        {\n            if(indegree[i]==0)\n                q.push(i);\n        }\n        \n        set<int> st[n]; //to avoid repetition of parent nodes \n        while(!q.empty())\n        {\n            \n            int cur=q.front(); \n            q.pop();\n            \n            for(auto it:adj_list[cur])\n            {\n                //inserting immediate parent node to each child of current node\n                st[it].insert(cur); \n                \n                //adds all the ancestors of the current node\n                for(auto it2:st[cur])\n                    st[it].insert(it2);\n                 \n                //adding to queue if indegree ==0\n                indegree[it]--;\n                if(indegree[it]==0)\n                q.push(it);\n            }\n        }\n        \n        //to store ans\n        vector<vector<int>> ans(n,vector<int>());\n        \n        //adding ancestors of each node to final ans vector\n        for(int i=0;i<n;++i)\n            ans[i]=vector<int>(st[i].begin(),st[i].end());\n        \n        \n        return ans; \n    }\n};\n```
['Breadth-First Search', 'Topological Sort', 'C']