描述

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

1. connect(a, b), 添加連接節(jié)點(diǎn) a, b 的邊.
2. query(a, b), 檢驗(yàn)兩個(gè)節(jié)點(diǎn)是否聯(lián)通

樣例

5 // n = 5
query(1, 2) 返回 false
connect(1, 2)
query(1, 3) 返回 false
connect(2, 4)
query(1, 4) 返回 true

代碼

public class ConnectingGraph { 

    private int[] father = null;

    private int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]);
    }
 
    // 初始化時(shí)父結(jié)點(diǎn)都是自己
    public ConnectingGraph(int n) {
        // initialize your data structure here.
        father = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            father[i] = i;
    }

    // 連接兩結(jié)點(diǎn)即為并查集合并操作
    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;
    }
        
    // 查詢兩結(jié)點(diǎn)是否相連，即為并查集查詢兩結(jié)點(diǎn)是否擁有相同父結(jié)點(diǎn)
    public boolean  query(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        return root_a == root_b;
    }
}