1557. Minimum Number of Vertices to Reach All Nodes

leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/

/*
    edges[i] = [from, to]
    n : node count
    
    // strategy
    1. bfs
    
*/
class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        
        Queue<Integer> q = new LinkedList<Integer>();
        boolean[] visit = new boolean[n];
        List<Integer> ans = new ArrayList<Integer>();
        
        for(int i=0; i<n; i++) {
            if(visit[i]) continue;
            
            // bfs start i
            q.offer(i);
            visit[i] = true;
            ans.add(i);
            
            // check visit
            while(!q.isEmpty()) {
                int node = q.poll();
                
                //adjacent
                for(List<Integer> edge : edges) {
                    if(edge.get(0) == node) {
                        if(!visit[edge.get(1)]) {
                            q.offer(edge.get(1));
                            visit[edge.get(1)] = true;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

단순 traverse 문제가 아님.

reachable 을 그루핑 하는것

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> ans = new HashSet<Integer>();
        
        // collect reachable set
        for(List<Integer> edge : edges) {
            set.add(edge.get(1));
        }
        
        for(List<Integer> edge : edges) {
            if(!set.contains(edge.get(0))) {
                ans.add(edge.get(0));
            }
        }
        
        return new ArrayList<Integer>(ans);
    }
}

leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/discuss/810214/Java-graph-in-degree-explained

Java, graph, in-degree, explained - LeetCode Discuss