并查集

约 105 个字 50 行代码 1 张图片 预计阅读时间 1 分钟

1. 基础概念

• 树\(\text{T}\)是由union-by-size构造出来的，总是将规模小的树合并到大的上，共\(N\)个节点，那么\(height(T)\leq \lfloor \log_2 N+1 \rfloor\)
  
• 时间复杂度：Find()的时间复杂度为\(O(\log N)\)
• 等价关系：
  • 自反性：\(\forall a \in S, a\ R\ a\)
  • 对称性：\(a\ R\ b \leftrightarrow b\ R\ a\)
  • 传递性：\((a\ R\ b) \wedge (b\ R\ c) \rightarrow a\ R\ c\)

2. 核心代码

void Initialize(int* s, int N){
    for(int i=0;i<N;i++){
        s[i]=-1;
    }
}
//朴素的Find函数
int Find(int x, int* s){
    while(s[x]>=0){
        x=s[x];
    }
    return x;
}

void setUnion(int* s, int r1, int r2){
    if(s[r1]<s[r2]){
        s[r1]+=s[r2];
        s[r2]=r1;
    }
    else{
        s[r2]+=s[r1];
        s[r1]=r2;
    }
}

//Find路径压缩
//递归
int FindPress(int x, int* s){
    if(s[x]<0){ //找到根了
        return x;
    }
    else{
        s[x]=FindPress(s[x],s);
        return s[x];
    }
}
//迭代
int FindPress2(int x,int *s){
    //先找到根
    int root;
    for(root=x;s[root]>=0;root=s[root]){

    }
    int trail;
    int lead;
    for(trail=x;trail!=root;trail=lead){
        lead=s[trail];
        s[trail]=root;
    }
    return root;
}

Comments