Python | Graph Traversal Techniques & Topological Sorting
see the Successfully Accepted Submission\n\n# Code\n\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        #
[see the Successfully Accepted Submission](https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/submissions/1303442848/?envType=daily-question&envId=2024-06-29)\n\n# Code\n```\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        # Build the adjacency list for the graph\n        graph = defaultdict(list)\n        for u, v in edges:\n            graph[u].append(v)\n        \n        # Create the reverse graph\n        reverse_graph = defaultdict(list)\n        for u, v in edges:\n            reverse_graph[v].append(u)\n        \n        # Perform topological sort\n        in_degree = [0] * n\n        for u in graph:\n            for v in graph[u]:\n                in_degree[v] += 1\n        \n        queue = deque([i for i in range(n) if in_degree[i] == 0])\n        topo_order = []\n        \n        while queue:\n            node = queue.popleft()\n            topo_order.append(node)\n            for neighbor in graph[node]:\n                in_degree[neighbor] -= 1\n                if in_degree[neighbor] == 0:\n                    queue.append(neighbor)\n        \n        # Compute ancestors using the reverse graph and topological order\n        ancestors = [set() for _ in range(n)]\n        \n        for node in topo_order:\n            for parent in reverse_graph[node]:\n                ancestors[node].add(parent)\n                ancestors[node].update(ancestors[parent])\n        \n        # Convert sets to sorted lists\n        result = [sorted(list(anc)) for anc in ancestors]\n        \n        return result\n        \n```\n\n# Step-by-Step Approach\n\n## Graph Representation\nRepresent the graph using an adjacency list. This helps in efficiently accessing the neighbors of any node.\n\n## Reverse Graph\nBuild the reverse graph where if there is an edge from `u` to `v` in the original graph, we add an edge from `v` to `u` in the reverse graph. This helps in tracing the ancestors.\n\n## Topological Sorting\nSince the graph is a DAG, perform a topological sort. Topological sorting of a DAG gives us a linear ordering of its nodes such that for every directed edge `u -> v`, `u` appears before `v` in the ordering. This helps in ensuring that when processing a node, all its ancestors have already been processed.\n\n## Ancestor Calculation\nUsing the reverse graph and the topologically sorted nodes, compute the ancestors. For each node, iterate through its neighbors in the reverse graph, and update the set of ancestors.\n\n# Explanation of the Code\n\n## Graph and Reverse Graph Construction\n- `graph` holds the original adjacency list.\n- `reverse_graph` holds the reverse adjacency list.\n\n## Topological Sort\n- We calculate the in-degree of each node.\n- Nodes with zero in-degree are added to the queue.\n- We process each node in the queue, updating the in-degree of its neighbors and adding neighbors with zero in-degree to the queue.\n- The result is a topological order of the nodes.\n\n## Ancestor Calculation\n- Using the topological order, for each node, we add its immediate parents from the reverse graph.\n- We also merge the ancestors of its parents to ensure all ancestors are included.\n\n## Result Formatting\n- Convert the set of ancestors for each node to a sorted list.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']