并查集求解共同根节点问题

题目链接:P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标准模板题解：

#include<stdio.h>
#define N 5001

int fa[N];//并查集数组

inline void init1(int n){
    for(int i=1;i<=n;i++)
        fa[i]=i;
}//初始化所有元素的父节点为本身

int find1(int x){
    if(fa[x]==x)
        return x;
    else
        return find1(fa[x]);
}//递归查找集合父节点

inline void merge1(int i,int j){
    fa[find1(i)]=find1(j);
}//合并集合(改变父节点)

int main(){
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    init1(n);
    for(int i=0;i<m;i++){
        int mi,mj;
        scanf("%d%d",&mi,&mj);
        merge1(mi,mj);
    }
    for(int i=0;i<p;i++){
        int pi,pj;
        scanf("%d%d",&pi,&pj);
        if(find1(pi)==find1(pj)
            printf("Yes\n");
        else
            printf("No\n");
    }
}

优化模板题解(路径压缩+按秩合并)：

#include<stdio.h>
#define N 5001

int fa[N];//并查集数组
int rank[N];//深度数组

inline void init2(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
        rank[i]=1;
    }
}//初始化所有元素的父节点为本身,并初始化深度为1

int find2(int x){
    if(fa[x]==x)
        return x;
    else{
        fa[x]=find2(fa[x]);
        return fa[x];
    }
}//路径压缩(将所有节点的父节点都设置为根节点)

inline void merge2(int i,int j){
    int x=find2(i),y=find2(j);
    if(rank[x]<rank[y])
        fa[x]=y;
    else
        fa[y]=x;
    if(rank[x]==rank[y]&&x!=y)
        rank[y]++;
}//按秩(深度)合并集合

int main(){
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    init2(n);
    for(int i=0;i<m;i++){
        int mi,mj;
        scanf("%d%d",&mi,&mj);
        merge2(mi,mj);
    }
    for(int i=0;i<p;i++){
        int pi,pj;
        scanf("%d%d",&pi,&pj);
        if(find2(pi)==find2(pj))
            printf("Yes\n");
        else
            printf("No\n");
    }
}

优化后的时间复杂度应该为O(logN).

参考文章：算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)