給一個圖中的 n 個節(jié)點, 記為 1 到 n .在開始的時候圖中沒有邊.
你需要完成下面兩個方法：
- connect(a, b), 添加一條連接節(jié)點 a, b的邊
- query(a), 返回圖中含 a 的聯(lián)通區(qū)域內(nèi)節(jié)點個數(shù)
樣例
5 // n = 5
query(1) 返回 1
connect(1, 2)
query(1) 返回 2
connect(2, 4)
query(1) 返回 3
connect(1, 4)
query(1) 返回 3
思路
589. 連接圖的follow up呐萨，只需增加一個 size 數(shù)組教硫，size[i] 表示以 i 結(jié)點為老大哥的所有結(jié)點個數(shù)衍菱，在合并兩個集合時脑奠，將被合并的 size 加到合并后的老大哥結(jié)點對應(yīng)的 size 上
代碼
public class ConnectingGraph2 {
private int[] father = null;
private int[] size = null;
private int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
public ConnectingGraph2(int n) {
// initialize your data structure here.
father = new int[n + 1];
size = new int[n + 1];
for (int i = 1; i <= n; ++i) {
father[i] = i;
size[i] = 1;
}
}
public void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
size[root_b] += size[root_a];
}
}
public int query(int a) {
int root_a = find(a);
return size[root_a];
}
}