[Topological Sort Tutorial] All Ancestors of a Node in a Directed Acyclic Graph
Topic :  Topological Sort\nTopological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u-v, vertex u
**Topic** :  Topological Sort\nTopological sorting for **Directed Acyclic Graph (DAG)** is a linear ordering of vertices such that for every directed edge u-v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a **DAG**. (GFG)\n\nHere\'s an example demonstrating Topological sorting on a graph:\n\n![image](https://assets.leetcode.com/users/images/fa0f0a92-da0d-4c0f-9d18-9e4785ff834d_1719620318.1530137.png)\n\nHere\'s how we can apply topological sorting:\n1. Identify vertices with no incoming edges (in-degree zero).\n2. Process the vertices.\n3. Update in-degrees.\n4. Repeat until all vertices are processed.\n\nWith the avove illustration:\n```\nStart with A.\nThen, proceed with B (since A -> B).\nNext, C (since A -> C, and B -> C).\nThen, D (since C -> D).\nFinally, E (since D -> E).\n```\n\n___\n\n## Solution\nFirst, we can represent our graph using an adjacency list named `graph`. We can do it as follow:\n```\n//pseudocode is written in C++\nvector<vector<int>> graph(n, vector<int>(0));\nfor(auto& e : edges) { //build adjecent list graph\n\t graph[e[0]].push_back(e[1]);\n }\n```\n\nSince the input graph is a **DAG** (Directed Acyclic Graph), Topological sort allows us to process each node in order. Besides constructing the graph, we also need to calculate the in-degree of each node.\n\nOne observation is that if there is a directed edge from node `u` to node `v` (denoted as `u -> v`), then any ancestor of `u` is also an ancestor of `v`. Additionally, `u` itself is also an ancestor of `v`.\n\nAs we perform topological sorting, we maintain a list of each node\'s ancestors. It\'s important to note that a node starting with a degree of 0 has no ancestors initially.\n\nIf we process an edge `u -> v` during topological sorting, we add all ancestors from `u`\'s list to `v`\'s list of ancestors. Simultaneously, we ensure to add `u` itself to `v`\'s list of ancestors. To avoid duplicates, each list of ancestors is implemented as a **set** data structure.\n\nFinally, after processing, we convert the list of ancestors back into the appropriate output structure as needed.\n<br/>\n```c++ []\nclass Solution {\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> graph(n, vector<int>(0));\n        vector<int> inDeg(n);\n        for(auto& e : edges) { //build adjecent list graph\n            graph[e[0]].push_back(e[1]);\n            inDeg[e[1]]++;\n        }\n        \n        queue<int> q;\n        for(int i = 0; i < n; i++) {\n            if(inDeg[i] == 0) {\n                q.push(i);\n            }\n        }\n        \n        vector<unordered_set<int>> ancestors(n);\n        while(q.size() > 0) {\n            int u = q.front(); q.pop();\n            for(int v : graph[u]) {\n                inDeg[v]--;\n                ancestors[v].insert(u);\n                for(int ancestor : ancestors[u]) {\n                    ancestors[v].insert(ancestor);\n                }\n                if(inDeg[v] == 0) {\n                    q.push(v);\n                }\n            }\n        }\n        \n        vector<vector<int>> ans(n);\n        for(int i = 0; i < n; i++) {\n            ans[i] = vector<int>(ancestors[i].begin(), ancestors[i].end());\n            sort(ans[i].begin(), ans[i].end());\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<List<Integer>> graph = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            graph.add(new ArrayList<>());\n        }\n        \n        int[] inDeg = new int[n];\n        for (int[] e : edges) {\n            graph.get(e[0]).add(e[1]);\n            inDeg[e[1]]++;\n        }\n        \n        Queue<Integer> q = new LinkedList<>();\n        for (int i = 0; i < n; i++) {\n            if (inDeg[i] == 0) {\n                q.add(i);\n            }\n        }\n        \n        List<Set<Integer>> ancestors = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            ancestors.add(new HashSet<>());\n        }\n        \n        while (!q.isEmpty()) {\n            int u = q.poll();\n            for (int v : graph.get(u)) {\n                inDeg[v]--;\n                ancestors.get(v).add(u);\n                for (int ancestor : ancestors.get(u)) {\n                    ancestors.get(v).add(ancestor);\n                }\n                if (inDeg[v] == 0) {\n                    q.add(v);\n                }\n            }\n        }\n        \n        List<List<Integer>> ans = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            List<Integer> list = new ArrayList<>(ancestors.get(i));\n            Collections.sort(list);\n            ans.add(list);\n        }\n        \n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        graph = [[] for _ in range(n)]\n        inDeg = [0] * n\n        \n        for e in edges:\n            graph[e[0]].append(e[1])\n            inDeg[e[1]] += 1\n        \n        q = deque()\n        for i in range(n):\n            if inDeg[i] == 0:\n                q.append(i)\n        \n        ancestors = [set() for _ in range(n)]\n        \n        while q:\n            u = q.popleft()\n            for v in graph[u]:\n                inDeg[v] -= 1\n                ancestors[v].add(u)\n                ancestors[v].update(ancestors[u])\n                if inDeg[v] == 0:\n                    q.append(v)\n        \n        ans = [[] for _ in range(n)]\n        for i in range(n):\n            ans[i] = sorted(list(ancestors[i]))\n        \n        return ans\n```\n```Go []\nfunc getAncestors(n int, edges [][]int) [][]int {\n    graph := make([][]int, n)\n\tinDeg := make([]int, n)\n\t\n\tfor _, e := range edges {\n\t\tgraph[e[0]] = append(graph[e[0]], e[1])\n\t\tinDeg[e[1]]++\n\t}\n\t\n\tq := make([]int, 0)\n\tfor i := 0; i < n; i++ {\n\t\tif inDeg[i] == 0 {\n\t\t\tq = append(q, i)\n\t\t}\n\t}\n\t\n\tancestors := make([]map[int]bool, n)\n\tfor i := 0; i < n; i++ {\n\t\tancestors[i] = make(map[int]bool)\n\t}\n\t\n\tfor len(q) > 0 {\n\t\tu := q[0]\n\t\tq = q[1:]\n\t\tfor _, v := range graph[u] {\n\t\t\tinDeg[v]--\n\t\t\tancestors[v][u] = true\n\t\t\tfor ancestor := range ancestors[u] {\n\t\t\t\tancestors[v][ancestor] = true\n\t\t\t}\n\t\t\tif inDeg[v] == 0 {\n\t\t\t\tq = append(q, v)\n\t\t\t}\n\t\t}\n\t}\n\t\n\tans := make([][]int, n)\n\tfor i := 0; i < n; i++ {\n\t\tans[i] = make([]int, 0, len(ancestors[i]))\n\t\tfor ancestor := range ancestors[i] {\n\t\t\tans[i] = append(ans[i], ancestor)\n\t\t}\n\t\tsort.Ints(ans[i])\n\t}\n\t\n\treturn ans\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer $n\n     * @param Integer[][] $edges\n     * @return Integer[][]\n     */\n    function getAncestors($n, $edges) {\n        $graph = array_fill(0, $n, []);\n        $inDeg = array_fill(0, $n, 0);\n        \n        foreach ($edges as $e) {\n            $graph[$e[0]][] = $e[1];\n            $inDeg[$e[1]]++;\n        }\n        \n        $q = [];\n        for ($i = 0; $i < $n; $i++) {\n            if ($inDeg[$i] == 0) {\n                $q[] = $i;\n            }\n        }\n        \n        $ancestors = array_fill(0, $n, []);\n        for ($i = 0; $i < $n; $i++) {\n            $ancestors[$i] = [];\n        }\n        \n        while (!empty($q)) {\n            $u = array_shift($q);\n            foreach ($graph[$u] as $v) {\n                $inDeg[$v]--;\n                $ancestors[$v][] = $u;\n                foreach ($ancestors[$u] as $ancestor) {\n                    if (!in_array($ancestor, $ancestors[$v])) {\n                        $ancestors[$v][] = $ancestor;\n                    }\n                }\n                if ($inDeg[$v] == 0) {\n                    $q[] = $v;\n                }\n            }\n        }\n        \n        $ans = array_fill(0, $n, []);\n        for ($i = 0; $i < $n; $i++) {\n            sort($ancestors[$i]);\n            $ans[$i] = $ancestors[$i];\n        }\n        \n        return $ans;\n    }\n}\n```\n```javascript []\n/**\n * @param {number} n\n * @param {number[][]} edges\n * @return {number[][]}\n */\nvar getAncestors = function(n, edges) {\n    let graph = new Array(n).fill(null).map(() => []);\n    let inDeg = new Array(n).fill(0);\n    \n    for (let e of edges) {\n        graph[e[0]].push(e[1]);\n        inDeg[e[1]]++;\n    }\n    \n    let q = [];\n    for (let i = 0; i < n; i++) {\n        if (inDeg[i] === 0) {\n            q.push(i);\n        }\n    }\n    \n    let ancestors = new Array(n).fill(null).map(() => new Set());\n    \n    while (q.length > 0) {\n        let u = q.shift();\n        for (let v of graph[u]) {\n            inDeg[v]--;\n            ancestors[v].add(u);\n            for (let ancestor of ancestors[u]) {\n                ancestors[v].add(ancestor);\n            }\n            if (inDeg[v] === 0) {\n                q.push(v);\n            }\n        }\n    }\n    \n    let ans = new Array(n);\n    for (let i = 0; i < n; i++) {\n        ans[i] = Array.from(ancestors[i]).sort((a, b) => a - b);\n    }\n    \n    return ans;\n};\n```\n\n**Complexity**:\n* Time Complexity : `O(n ^ 2 log(n) + n * m)`\n* Space Complexity : `O(n ^ 2)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['C', 'PHP', 'Python', 'Java', 'Go', 'JavaScript']