LC1557 可以到达所有点的最少点数目

本文主要是介绍LC1557 可以到达所有点的最少点数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题卡在如何选择方案。。。我想太复杂了，以下是我卡在如何选择方案的算法

class Solution {int N = 100010, M = N * 2, idx = 0, n；  int[] e = new int[M], ne = new int[M], h = new int[N];public void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx ++;}List<Integer> ans;ArrayList<Integer>[] save;public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {Arrays.fill(h, -1);this.n = n;for(List<Integer> e) {add(e[0], e[1]);}ans = new ArrayList<>();save = new ArrayList[n + 1];for(int i = 0;i < n;i ++) {save[i] = new ArrayList<>();find(i);}}public void find(int now) {ArrayDeque<Integer> aq = new ArrayDeque<>();aq.offer(now);boolean[] st = new int[n + 1];st[now] = true;save[now].add(now);while(!aq.isEmpty()) {int a = aq.poll();for(int i = h[a];i != -1;i = ne[i]) {int next = e[i];if(!st[next]) {st[next] = true;save[now].add(next);aq.offer(next);}}}}
}

如果做过这道题的人就会知道我原先想的有多复杂，那么其实可以不用这么复杂的。。。

这个可以到达所有点的最少点数目，换个思路，到达不了的点是不是就是必须出发的点，也就是入度为0的点。。。从这些入度为0的点出发，是不是一定会达到入度不为0的点，所以我们只要统计出来入度为0的点即可。

class Solution {public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {Set<Integer> set = new HashSet<>();ArrayList<Integer> ans = new ArrayList<>();int m = edges.size();for(List<Integer> l : edges){set.add(l.get(1));}for(int i = 0; i < n; i++){if(!set.contains(i)) ans.add(i);}return ans;}
}