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.
1import java.util.*;
2
3public class Ancestors {
4 public List<List<Integer>> getAncestors(int n, int[][] edges) {
5 List<List<Integer>> graph = new ArrayList<>();
6 int[] indegree = new int[n];
7 List<Set<Integer>> ancestors = new ArrayList<>();
8
9 for (int i = 0; i < n; i++) {
10 graph.add(new ArrayList<>());
11 ancestors.add(new TreeSet<>());
12 }
13
14 for (int[] edge : edges) {
15 graph.get(edge[0]).add(edge[1]);
16 indegree[edge[1]]++;
17 }
18
19 Queue<Integer> zeroIndegree = new LinkedList<>();
20 for (int i = 0; i < n; i++) {
21 if (indegree[i] == 0) {
22 zeroIndegree.add(i);
23 }
24 }
25
26 while (!zeroIndegree.isEmpty()) {
27 int node = zeroIndegree.poll();
28 for (int neighbor : graph.get(node)) {
29 ancestors.get(neighbor).add(node);
30 ancestors.get(neighbor).addAll(ancestors.get(node));
31 if (--indegree[neighbor] == 0) {
32 zeroIndegree.add(neighbor);
33 }
34 }
35 }
36
37 List<List<Integer>> result = new ArrayList<>();
38 for (Set<Integer> ancestorSet : ancestors) {
39 result.add(new ArrayList<>(ancestorSet));
40 }
41
42 return result;
43 }
44 // Example usage
45 // public static void main(String[] args) {
46 // Ancestors sol = new Ancestors();
47 // int n = 8;
48 // int[][] edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
49 // List<List<Integer>> result = sol.getAncestors(n, edges);
50 // // Output result
51 // }
52}This Java implementation uses ArrayList and TreeSet to represent the graph and the ancestor collections. TreeSet automatically maintains natural order of elements (sorting), which ensures the ancestors are added in ascending order, reducing the need for post sorting in result arrays. The queue manages nodes with zero indegree to apply the topological sort strategy efficiently.
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.