Find the Weak Connected Component in the Directed Graph

Find the Weak Connected Component in the Directed Graph

17%

Accepted

Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)

Have you met this question in a real interview? 

Yes

Example

Given graph:

A----->B  C
 \     |  | 
  \    |  |
   \   |  |
    \  v  v
     ->D  E <- F

Return {A,B,D}, {C,E,F}. Since there are two connected component which are {A,B,D} and {C,E,F}

Note

Sort the element in the set in increasing order

public class Solution {
    /**
     * @param nodes a array of Directed graph node
     * @return a connected set of a directed graph
     */
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        // Write your code here
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(DirectedGraphNode node : nodes){
            for(DirectedGraphNode n : node.neighbors){
                int fa = find(map, node.label);
                int ch = find(map, n.label);
                map.put(fa, ch);
            }
        }
        HashMap<Integer, ArrayList<Integer>> record = new HashMap<Integer, ArrayList<Integer>>();
       
        for(DirectedGraphNode node : nodes){
            int val = find(map, node.label);
            if(!record.containsKey(val)){
                record.put(val, new ArrayList<Integer>());
            }
            record.get(val).add(node.label);
        }
       
        for(int key : record.keySet()){
            ArrayList<Integer> sub = new ArrayList<Integer>();
            sub.addAll(record.get(key));
            res.add(sub);
        }
        return res;
       
    }
   
    private int find(HashMap<Integer, Integer> map, int v){
        if(!map.containsKey(v)){
            map.put(v, v);
            return v;
        }
        while(map.get(v) != v) v = map.get(v);
        return v;
    }
}