并查集

并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题

• 连接问题

find

• find操作返回该节点连接的节点

int find(int p) {
    return data[p];
}

另外一种实现，通过判断两个节点是否拥有同样的祖先来判断是否相连

while (p != parent[p]) {
    p = parent[p];
}
return p;

isConnected

• 判断两个节点是否连接在一起的（判断这两个节点是否连接了同一个节点）

boolean isConnected(int p, int q) {
    return find(p) == find(q);
}

union

• 连接两个节点（将一个节点指向另外一个节点）

int pid = find(p);
int qid = find(q);
if (pid == qid){
    return;
}
for (int i = 0; i < count; i++) {
    if (data[i]==pid){
        data[i]=qid;
    }
}

使用另外一种实现的union

int qRoot = find(p);
int pRoot = find(q);
if (qRoot == pRoot){
    return;
}
parent[pRoot]=qRoot;

基于size的优化，维护一个size数组，代表以i为根的集合的元素个数

if (sz[pRoot]<sz[qRoot]){        
    parent[pRoot] = qRoot;
    sz[qRoot]+=sz[pRoot];
}else {
    parent[qRoot] = pRoot;
    sz[qRoot]+=sz[pRoot];
}

使用rank来决定谁连接谁

if (rank[pRoot] < rank[qRoot]) {
    parent[pRoot] = qRoot;
} else if ((rank[pRoot] > rank[qRoot])) {
    parent[qRoot] = pRoot;
} else {
    parent[pRoot] = qRoot;
    rank[qRoot] += 1;
}

路径压缩

• find

while (p != parent[p]) {
    parent[p]=parent[parent[p]];
    p = parent[p];
}
return p;