# Lintcode 591 - Connecting Graph III

解法一 - Union Find

我們可以在 class 中額外儲存一個當前的集合個數，每次 connect 若成功就減 1，實作如下：

class ConnectingGraph3 {
public:
    ConnectingGraph3(int n) {
        parent.reserve(n+1);
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        setNumber = n;
    }

    int find(int node) {
        if(node == parent[node]) {
            return node;
        }

        parent[node] = find(parent[node]);
        return parent[node];
    }

    /**
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    void connect(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if(rootA != rootB) {
            parent[rootA] = rootB;
            --setNumber;
        }
    }

    /**
     * @return: An integer
     */
    int query() {
        return setNumber;
    }

private:
    vector<int> parent;
    int setNumber;
};