并查集

并查集是一种树型的数据结构,用于处理一些不交集(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;

results matching " "

No results matching " "

results matching " "

No results matching " "