今天学习了神奇的并查集，UnionFind，试着做了几道之前用BFS/DFS的算法题，感觉超好用！
UnionFind的基础运用：
- 创建一个UnionFind
- 查找某元素所在group的大哥
- 连接两个元素
- 判断两个元素是否在同一个group中
那我们来看看题目吧！
Connecting Graph
Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning. You need to support the following method:
- connect(a, b), add an edge to connect node a and node b.
2.query(a, b), check if two nodes are connected
public class ConnectingGraph {
private int[] father = null;
private int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
public ConnectingGraph(int n) {
// initialize your data structure here.
father = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
father[i] = i;
}
}
public void connect(int a, int b) {
// Write your code here
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB;
}
}
public boolean query(int a, int b) {
// Write your code here
int rootA = find(a);
int rootB = find(b);
return (rootA == rootB);
}
}
