今天學(xué)習(xí)了神奇的并查集僻澎，UnionFind，試著做了幾道之前用BFS/DFS的算法題十饥，感覺(jué)超好用窟勃！
UnionFind的基礎(chǔ)運(yùn)用：
- 創(chuàng)建一個(gè)UnionFind
- 查找某元素所在group的大哥
- 連接兩個(gè)元素
- 判斷兩個(gè)元素是否在同一個(gè)group中
那我們來(lái)看看題目吧！
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);
}
}
