首页 > 代码库 > 并查集模板

并查集模板

#include<cstdio>
#include<iostream>
using namespace std;
int f[1001];
int x,y;
int m,n,q,i;
int find(int x)
{
     if(f[x]!=x) f[x]=find(f[x]);
     return f[x];    
} 
void hb(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a!=b)
    f[a]=b;
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
    f[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        hb(x,y);
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>x>>y;
        if(find(x)==find(y))
          printf("YES\n");
        else 
          printf("NO\n");
    }
} 

我爱我自己?!!

并查集模板