Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

Notice
Each connected component should sort by label.

Example
Given graph:

1
2
3
4
5
6
A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E

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

Union Find

先做的lintcode 432, 这两个题目的Union Find解法基本一样。

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
40
41
public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
    HashMap<Integer, Integer> fathers = new HashMap<>();
    
    for (UndirectedGraphNode node : nodes) {
        fathers.put(node.label, node.label);
    }
    for (UndirectedGraphNode node : nodes) {
        int fax = find(fathers, node.label);
        for (UndirectedGraphNode 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;
}