并查集模板

_pzy · 2025-05-17 14:36:39 · 算法·理论

核心思想

对两个树进行合并与查找操作，可以判断两个节点的连通性。

路径压缩代码

#include<bits/stdc++.h>
using namespace std;
int n,m,q,f[20005];
int find(int x)
{

    int r=x,t;
    while(f[r]!=r)
    {
        r=f[r];
    }
    while(x!=r)
    {
        t=x;
        x=f[x];
        f[t]=r;
    }
    return r;
}
void merge(int x,long y)
{
    int a,b;
    a=find(x);
    b=find(y);
    if(a!=b)
    {
        f[b]=a;
    }
    return ;
}
int main()
{
    cin>>n>>m>>q;
    int x,y;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    } 
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        merge(x,y);
    }
    while(q--)
    {
        cin>>x>>y;
        if(find(x)==find(y))
        {
            cout<<"Yes\n";
        }
        else
        {
            cout<<"No\n";
        }
    }
    return 0;
}