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.)

Notice
Sort the element in the set in increasing order

Example
Given graph:

1
2
3
4
5
6
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}

Union Find

又是一道Union Find的题目，当然这种题目DFS和BFS也都可以做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
    HashMap<Integer, Integer> fathers = new HashMap<>();
    for (DirectedGraphNode node : nodes) {
        fathers.put(node.label, node.label);
    }
    for (DirectedGraphNode node : nodes) {
        int fax = find(fathers, node.label);
        for (DirectedGraphNode neighbor : node.neighbors) {
            int fay = find(fathers, neighbor.label);
            if (fax != fay) {
                fathers.put(fay, fax);
            }
        }
    }
    HashMap<Integer, ArrayList<Integer>> ans = new HashMap<>();
    for (Map.Entry<Integer, Integer> entry : fathers.entrySet()) {
        int fa = find(fathers, entry.getKey());
        if (!ans.containsKey(fa)) {
            ans.put(fa, new ArrayList<Integer>());
        }
        ans.get(fa).add(entry.getKey());
    }
    List<List<Integer>> res = new ArrayList<>();
    for (List<Integer> v : ans.values()) {
        Collections.sort(v);
        res.add(v);
    }
    return res;
}
public int find(HashMap<Integer, Integer> fathers, int label) {
    int fa = fathers.get(label);
    while (fa != fathers.get(fa)) {
        fa = fathers.get(fa);
    }
    return fa;
}