并查集

对于求连通方面的东西，可以使用并查集，并查集很大一部分思想是使用一个唯一id编号，对同一个连接标注相同的号，这种想法在求连通块中非常常见。

class unionSet {
public:
    int *id;//用于确定连通
    int cnt;//唯一id
    int N;//点的数量
    unionSet(int n){
        N = n;
        cnt = n;
        id = new int[n];
        for(int i = 0; i < n;++i){
            id[i] = i;//初始化为每个点一个连通编号
        }
    }
    int _count(){return cnt;}
    bool connected(int p, int q){
        return _find(p) == _find(q);
    }
    int _find(int p){return id[p];}
    void _union(int p, int q){
        int pid = _find(p);
        int qid = _find(q);
        if(pid == qid) return;
        for(int i = 0; i < N;++i){//将两个点的连通区域合并成一个，就是使用同一个id连通编号
            if(id[i] == pid)
                id[i] = qid;
        }
        --cnt;
    }
};