Hexo

Question

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from i, to] represents a directed edge from node from i to node to i .

Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Answer

由于是有向无环图（Directed acyclic graph），因此直接计算图内的入度为0的节点即可。
每条路径都需要从入度为0的点开始。

Code

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ret = new ArrayList<>();
        int[] inDegrees = new int[n];
        for(List<Integer> edge : edges){
            inDegrees[edge.get(1)]++;
        }
        for(int i = 0; i < n; i++){
            if(inDegrees[i] == 0) ret.add(i);
        }
        return ret;
    }
}