LeetCode刷题.14(不用算法解决1557. 可以到达所有点的最少点数目)

给你一个?有向无环图?，?n?个节点编号为?0?到?n-1?，以及一个边数组?edges?，其中?edges[i] = [fromi, toi]?表示一条从点??fromi?到点?toi?的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]

输出：[0,3]

解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。

示例 2：

输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]

输出：[0,2,3]

解释：注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，这些点都能到达节点 1 和 4 。

提示：

2 <= n <= 10^5

1 <= edges.length <= min(10^5, n * (n - 1) / 2)

edges[i].length == 2

0 <= fromi,?toi < n

所有点对?(fromi, toi)?互不相同。

解题思路：

? ? ? ? 若一个图中的某一节点没有入度，则说明其它节点访问不到它，那么要遍历所有节点，他必须当第一个出发点，否则无法遍历它，而有入度的总会有节点能访问到，拿示例 1图来说：

? ? ? ? 图中打×的表示没有入度的节点，打√的则是有入度的节点

? ? ? ? 从节点0出发：0->1? ? ? ? 0->2->5

? ? ? ? 从节点1出发：1

? ? ? ? 从节点2出发：2->5

? ? ? ? 从节点3出发：3->4->2->5

? ? ? ? 从节点4出发：4->3->5

? ? ? ? 从节点5出发：5

? ? ? ? 由分析可知：从所有有入度的节点(1,2,4,5)出发只会遍历1,2,4和5，因为入度不为零的点总可以由某个无入度的点到达，所以这些点不包括在最小的合法点集合当中。而从所有无入度节点(0,3)出发则能将节点全部遍历，因此我们只需要返回所有无入度的节点即可。

代码实现：

? ? ? ? 1.哈希表记录：

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        //哈希表记录所有有入度的点
        Set<Integer> hs=new HashSet<>();
        for(int x=0;x<edges.size();x++){
            hs.add(edges.get(x).get(1));
        }
        List<Integer> l=new ArrayList<>();
        //从零遍历，若该节点不在哈希表中说明，它为无入度节点，则存放到l中
        for(int x=0;x<n;x++){
            if(!hs.contains(x)){
                l.add(x);
            }
        }
        return l;
    }
}

? ? ? ? 2.运用boolean数组记录：

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        //运用boolean类型数组存放，若有入度则为true
        boolean []b=new boolean[n];
        for(int x=0;x<edges.size();x++){
            b[edges.get(x).get(1)]=true;
        }
        List<Integer> l=new ArrayList<>();
        //false放进l中
        for(int x=0;x<n;x++){
            if(!b[x]) l.add(x);
        }
        return l;
    }
}