2192. All Ancestors of a Node in a Directed Acyclic Graph

,

Topological Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Set<Integer>> resultList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            resultList.add(new TreeSet<>());
        }

        int[] inDegrees = new int[n];
        List<List<Integer>> nodeToNodeListList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            nodeToNodeListList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            inDegrees[to]++;
            nodeToNodeListList.get(from).add(to);
        }

        Queue<Integer> zeroInDegreeNodeQueue = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                zeroInDegreeNodeQueue.offer(i);
            }
        }

        while (!zeroInDegreeNodeQueue.isEmpty()) {
            int from = zeroInDegreeNodeQueue.poll();
            for (int to : nodeToNodeListList.get(from)) {
                resultList.get(to).addAll(resultList.get(from));
                resultList.get(to).add(from);
                if (--inDegrees[to] == 0) {
                    zeroInDegreeNodeQueue.offer(to);
                }
            }
        }

        return resultList.stream().map(ArrayList::new).collect(Collectors.toList());
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<List<Integer>> reversedEdgeList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            resultList.add(new ArrayList<>());
            reversedEdgeList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int from = edge[1], to = edge[0];
            reversedEdgeList.get(from).add(to);
        }

        boolean[] visited = new boolean[n]; // 防止重复遍历，且记录访问过的节点，遍历完成后通过该数组构建结果集，能够保证节点有序
        // 从终点出发
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited, false);
            dfs(reversedEdgeList, visited, i);
            visited[i] = false;
            for (int j = 0; j < n; j++) {
                if (visited[j]) {
                    resultList.get(i).add(j);
                }
            }
        }

        return resultList;
    }

    private void dfs(List<List<Integer>> reversedEdgeList, boolean[] visited, int to) {
        visited[to] = true;

        for (int from : reversedEdgeList.get(to)) {
            if (visited[from]) {
                continue;
            }

            dfs(reversedEdgeList, visited, from);
        }
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<List<Integer>> edgeList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            resultList.add(new ArrayList<>());
            edgeList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            edgeList.get(from).add(to);
        }

        int[] visited = new int[n]; // 防止重复遍历，且记录的值为起点，便于在 DFS 过程中构建结果集
        Arrays.fill(visited, -1);
        // 从起点出发
        for (int i = 0; i < n; i++) {
            dfs(resultList, edgeList, visited, i, i);
        }

        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<List<Integer>> edgeList, int[] visited, int from, int ancestor) {
        visited[from] = ancestor;

        for (int to : edgeList.get(from)) {
            if (visited[to] == ancestor) {
                continue;
            }

            resultList.get(to).add(ancestor);
            dfs(resultList, edgeList, visited, to, ancestor);
        }
    }
}

References

2192. All Ancestors of a Node in a Directed Acyclic Graph