Sponsored
Sponsored
This approach involves the following steps:
Time Complexity: O(V + E), where V is the number of nodes and E is the number of edges, since we're effectively traversing all nodes and edges.
Space Complexity: O(V + E), due to the storage needed for the graph representation and the ancestors lists.
1from collections import defaultdict, deque
2
3def getAncestors(n, edges):
4 graph = defaultdict(list)
5 indegree = [0] * n
6 ancestors = [set() for _ in range(n)]
7
8 # Build graph and calculate in-degrees
9 for frm, to in edges:
10 graph[frm].append(to)
11 indegree[to] += 1
12
13 # Topological Sort
14 zero_indegree = deque()
15 for i in range(n):
16 if indegree[i] == 0:
17 zero_indegree.append(i)
18
19 while zero_indegree:
20 node = zero_indegree.popleft()
21 for neighbor in graph[node]:
22 ancestors[neighbor].add(node)
23 ancestors[neighbor].update(ancestors[node])
24 indegree[neighbor] -= 1
25 if indegree[neighbor] == 0:
26 zero_indegree.append(neighbor)
27
28 # Convert sets to sorted lists
29 return [sorted(list(ancestor)) for ancestor in ancestors]
30
31# Example usage
32n = 8
33edges = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
34print(getAncestors(n, edges))This solution uses a DFS-based topological sort to process each node in a DAG. We represent the graph as an adjacency list and maintain an indegree count. Nodes with no incoming edges are processed first, during which their ancestors are propagated to their children nodes. This is done until all nodes are processed, yielding a set of ancestors which we then convert to a sorted list for each node to meet the problem requirement.
Here, we reverse the edges in the graph and then perform a DFS for each node to find all reachable nodes, which now represent ancestors. This is an implementation that directly finds ancestors by traversing upwards in the graph via reversed edges:
Time Complexity: O(V * (V + E)), due to performing DFS from every node and having potential to traverse the full graph per DFS call.
Space Complexity: O(V + E), where V storage comes from graph information and visited nodes tracking.
1import java.
Similar in essence to the other implementations, this Java solution tackles the problem by reversing graph edges and undertaking DFS from each node. The graph is initially represented with reversed direction, and a set-based approach keeps ancestor uniqueness, eventually yielding sorted lists for the final result.