leetcode-1557. 可以到达所有点的最少点数目

使用逆向集合存储点的入度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> result = new ArrayList<>();
        List<Set<Integer>> rgraph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            rgraph.add(new HashSet<>());
        }

        for (int i = 0; i < edges.size(); i++) {
            rgraph.get(edges.get(i).get(1)).add(edges.get(i).get(0));
        }

        for (int i = 0; i < n; i++) {
            if (rgraph.get(i).size() == 0) {
                result.add(i);
            }
        }
        return result;
    }
}

题解思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ans = new ArrayList<>();
        
        // 存储所有入度不为0的点
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < edges.size(); i++){
            set.add(edges.get(i).get(1));
        }
        
        for(int i = 0; i < n; i++){
            if(!set.contains(i)){
                ans.add(i);
            }
        }
        return ans;
    }
}