Topo sort Kahn's algo+counting sort||54ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nCompute indegree for every vertex,  use Kahn\'s algorithm to find ancestors for each ve
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCompute indegree for every vertex,  use Kahn\'s algorithm to find ancestors for each vertex.\n\njust use std::vector & sorting to give the desired answer. For comparison, Kahn\'s algorthm with std::set is also made which is slow.\n \nAn approach uses Kahn\'s algorthm with counting sort(in fact a variant) with running time 54ms beating 100%. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nToplogical sort can solve the following questions\n[207. Course Schedule](https://leetcode.com/problems/course-schedule/solutions/3756937/w-explanation-c-dfs-vs-bfs-kahn-s-algorithm/)\n[210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)\n[1203. Sort Items by Groups Respecting Dependencies\n](https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/solutions/3933825/c-using-bfs-kahn-s-algorithm-vs-dfs-beats-97-67/)\n[1203. Sort Items by Groups Respecting Dependencies| Please Turn English Subtitles if Neceesary]\n[https://youtu.be/vdar3a_ZdCI](https://youtu.be/vdar3a_ZdCI)\nKahn\'s Algorithm is BFS method by removing the edges and decreasing the indegrees. \n1. Need 2 containers `deg` for indegree & `adj` for adjacent list for each vertex.\n2. Use a loop to deal `deg` & `adj`\n3. Kahn\'s algorithm needs a queue `q` which is a BFS algorithm\n4. vertices without ancestors, i.e. deg[v]=0 are pushed to `q`\n5. Use a conditional loop as long as `q` is not empty do the following:\n```\nv = q.front(); q.pop();\n            \nfor (int w : adj[v]) {\n    auto& aw=ancestor[w];\n    // Add v and all ancestors of v to the ancestors[w]\n    aw.push_back(v);\n    aw.insert(aw.end(), ancestor[v].begin(), ancestor[v].end());\n                \n    // Sort and remove duplicates\n    sort(aw.begin(), aw.end());\n    int sz=1, az=aw.size();\n                \n    for (int i=1; i<az; i++) {\n        if (aw[i]!=aw[i-1]) \n            aw[sz++]=aw[i];\n    }\n    aw.resize(sz);\n\n    if (--deg[w] == 0) q.push(w); //push vertex with 0 deg\n```\n6. `ancestor` is the answer\n7.  Comparison of  C++ codes\n\n|Methods|Elapsed time|Record|Memomory|\n|---|---|---|---|\n| Kahn\'s algo+sorting & removing duplicates| 83ms|98.13%|54.86MB|\n|Kahn\'s algo with set|345ms|38.42%|144.22MB|\n|Kahn\'s algo + counting sort using bitset|54ms|100%|83.80MB|\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2\\log n +m)\\to O(n^2+m)$$ where $m=|edges|$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# Code  Kahn\'s algo+sorting||C++ 83ms Beats 98.13%\n```\nclass Solution {\npublic:\n    static vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<int> deg(n, 0);\n        vector<vector<int>> adj(n);\n\n        for (auto& e: edges) {//Build adjacent list\n            int v=e[0], w=e[1];\n            adj[v].push_back(w);\n            deg[w]++;// indegree\n        }\n\n        queue<int> q;\n        for(int i=0; i<n; i++)\n            if (deg[i]==0) q.push(i);// vertices without ancestors\n\n        vector<vector<int>> ancestor(n);\n        \n        while (!q.empty()) {\n            int v = q.front();\n            q.pop();\n            \n            for (int w : adj[v]) {\n                auto& aw=ancestor[w];\n                // Add v and all ancestors of v to the ancestors[w]\n                aw.push_back(v);\n                aw.insert(aw.end(), ancestor[v].begin(), ancestor[v].end());\n                \n                // Sort and remove duplicates\n                sort(aw.begin(), aw.end());\n                int sz=1, az=aw.size();\n                \n                for (int i=1; i<az; i++) {\n                    if (aw[i]!=aw[i-1]) \n                        aw[sz++]=aw[i];\n                }\n                aw.resize(sz);\n\n                if (--deg[w] == 0) q.push(w); //push vertex with 0 deg\n            }\n        }\n        \n        return ancestor;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ Kahn\'s algorthm with std::set||345 ms Beats 38.42%\n```\nclass Solution {\npublic:\n    static vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<int> deg(n, 0);\n        vector<vector<int>> adj(n);\n\n        for (auto& e: edges) {//Build adjacent list\n            int v=e[0], w=e[1];\n            adj[v].push_back(w);\n            deg[w]++;// indegree\n        }\n        queue<int> q;\n        for(int i=0; i<n; i++)\n            if (deg[i]==0) q.push(i);\n\n        vector<set<int>> ancestor(n);\n        while(!q.empty()){\n            int v=q.front();\n            q.pop();\n            for (int w : adj[v]) {\n                // Add v and all ancestors of v to the ancestors of w\n                ancestor[w].insert(v);\n                ancestor[w].insert(ancestor[v].begin(), ancestor[v].end());\n\n                if (--deg[w] == 0) q.push(w);  //push vertex with 0 deg\n            }\n        }\n        vector<vector<int>> ans(n);\n        for(int i=0; i<n; i++)\n            ans[i]=vector<int>(ancestor[i].begin(), ancestor[i].end());\n        return ans;\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ Kahn\'s algo+counting sort||54ms Beats 100%\n```\nclass Solution {\npublic:\n    static vector<vector<int>> getAncestors(const int n,\n                                            const vector<vector<int>>& edges) {\n        vector<int> deg(n, 0);\n        vector<vector<int>> adj(n);\n\n        for (auto& e : edges) { // Build adjacent list\n            const int v = e[0], w = e[1];\n            adj[v].push_back(w);\n            deg[w]++; // indegree\n        }\n\n        queue<int> q;\n        for (int i = 0; i < n; i++)\n            if (deg[i] == 0)\n                q.push(i);\n\n        vector<vector<int>> ancestor(n);\n\n        while (!q.empty()) {\n            const int v = q.front();\n            q.pop();\n\n            //bitset for v and all ancestors of v\n            bitset<1000> S_v=0;\n            for (const int x : ancestor[v])\n                S_v[x] = 1;\n            int m0 = v, mN = v;// min & max for v and all ancestors of v\n            S_v[v]=1;\n            if (ancestor[v].size()) {\n                m0 = min(m0, ancestor[v][0]);\n                mN = max(mN, ancestor[v].back());\n            }\n            for (const int w : adj[v]) {\n                auto& aw = ancestor[w];\n                // Add v and all ancestors of v to the ancestors[w]\n                bitset<1000> S = S_v;\n                \n                for (int x : aw)\n                    S[x] = 1;\n                if (aw.size()) {\n                    m0 = min(m0, aw[0]);\n                    mN = max(mN, aw.back());\n                }\n                \n                aw.resize(mN+1);\n                int sz = 0;\n                for (int x = m0; x <= mN; x++) {\n                    if (S[x]) aw[sz++] = x;\n                }\n                aw.resize(sz);\n\n                if (--deg[w] == 0)\n                    q.push(w); // push vertex with 0 deg\n            }\n        }\n\n        return ancestor;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Bit Manipulation', 'Graph', 'Topological Sort', 'C', 'Sorting', 'Counting Sort']