描述

給一個(gè)圖中的 n 個(gè)節(jié)點(diǎn), 記為 1 到 n .在開始的時(shí)候圖中沒有邊.
你需要完成下面兩個(gè)方法：

1. connect(a, b), 添加一條連接節(jié)點(diǎn) a, b的邊
2. query(a), 返回圖中含 a 的聯(lián)通區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(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，只需增加一個(gè) size 數(shù)組，size[i] 表示以 i 結(jié)點(diǎn)為老大哥的所有結(jié)點(diǎn)個(gè)數(shù)，在合并兩個(gè)集合時(shí)，將被合并的 size 加到合并后的老大哥結(jié)點(diǎn)對(duì)應(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];
    }
}