并查集模板写法

class UnionFind {
private:
	int cnt;             // 连通分量
    vector<int> parent;  //x父节点为parent[x]
public:
    UnionFind(int n) {
        cnt = n;
        parent.resize(n);
        // 开始时,每个节点是自己的父节点
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
// 连通两个节点
void connect(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) return;
    parent[rootP] = rootQ; // 两个树的根节点合并
    cnt--;
}
 
// 找到x的根节点
int find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}
 
//判断p, q是否连通
bool isConnected(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
}
 
// 返回有多少连通分量
int count() {
    return cnt;
}

};