Union Find
Union Find
通畅Union Find出现在Graph问题中，用一个father array实现即可。可以实现的功能：
- 查询两元素是否在同一集合 2. 合并两个元素所在集合 3. 查询某元素所在集合的元素个数（派生） 4. 查询当前的集合个数（派生）
- Connecting Graph
- Connecting Graph II
- Connecting Graph III
- Number of Islands
- Number of Islands II
- Graph Valid Tree
- Longest Consecutive Sequence
- Friend Circles
- Number of Connected Components in an Undirected Graph
Code
1 public UnionFind(int n){
2 father = new int[n + 1];
3 for (int i = 1; i <= n; i++){
4 father[i] = i;
5 }
6 }
7
8 private int find(int x){
9 if (father[x] == x){
10 return x;
11 }
12 return father[x] = find(father[x]);
13 }
14
15 private void union(int a, int b){
16 int rootA = find(a);
17 int rootB = find(b);
18 if (rootA != rootB){
19 father[rootA] = rootB;
20 }
21 }