Given n nodes in a graph labeled from1 to `n. There is no edges in the graph at beginning.
You need to support the following method:
1.connect(a, b), add an edge to connect node a and node b.
2.query(a, b), check if two nodes are connected
Example
5 // n = 5
query(1, 2) return false
connect(1, 2)
query(1, 3) return false
connect(2, 4)
query(1, 4) return true
這題就是實現(xiàn)一個最基礎(chǔ)的Union Find. 需要新建一個int[] father來代表每個節(jié)點的老板節(jié)點祝迂。注意這里的find()是路徑壓縮后的方法九妈，時間復(fù)雜度是O(1). 而且connect一定要記住翅敌，是connect兩個節(jié)點的大老板節(jié)點追他。也就是老師說的：“老大哥之間合并玷过，跟小弟沒關(guān)系”。 同時，query的時候也是查看兩個節(jié)點的根節(jié)點（大老板，老大哥）是不是一樣遮糖，而跟他們本身沒有關(guān)系。
public class ConnectingGraph {
int[] father;
public ConnectingGraph(int n) {
// initialize your data structure here.
father = new int[n + 1];
for (int i = 1; i < n + 1; i++){
father[i] = i;
}
}
public void connect(int a, int b) {
// Write your code here
int c = find(a);
int d = find(b);
if (c != d){
father[d] = c;
}
}
public boolean query(int a, int b) {
// Write your code here
int c = find(a);
int d = find(b);
if (c == d){
return true;
}
return false;
}
private int find(int a){
if (father[a] == a){
return a;
}
return father[a] = find(father[a]);
}
}
