Leetcode 1557

This is a tropological sort kind of problem, we can't use union find because we would union things all together. Instead, we should just care about nodes that aren't reachable from other nodes.

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        boolean[] pointed = new boolean[n];
        for(List<Integer> edge : edges){
            pointed[edge.get(1)] = true; // this node can be reached from other nodes
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < n; i ++){
            // any nodes cant be reached from other nodes we just add into res
            if(!pointed[i]) res.add(i);
        }
        return res;
    }
}