P1551 亲戚

题目链接：落谷

题目链接：TFLS OJ

落谷题解（具体分析见慎入潜出P239）

#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int fu[5010];
int find(int x){//查询是否是同一个家族
    if(x==fu[x])    return x;
    return fu[x]=find(fu[x]);
}
void connect(int x,int y){
    int f1=find(x);
    int f2=find(y);
    if(f1!=f2)
        fu[f1]=f2;
}
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)//初始化，每个人为一个家族
        fu[i]=i;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        connect(x,y);//连接俩氢气
    }
    for(int i=0;i<p;i++){
        int x,y;
        cin>>x>>y;
        if(find(x)==find(y))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

OJ题解

#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int fu[10500000];
int find(int x){//查询是否是同一个家族
    if(x==fu[x])    return x;
    return fu[x]=find(fu[x]);
}
void connect(int x,int y){
    int f1=find(x);//
    int f2=find(y);
    if(f1!=f2)
        fu[f1]=f2;
}
int main(){
    scanf("%d%d",&n,&m);//OJ里cin,cout会超时（
    for(int i=1;i<=n;i++)//初始化家族，每人为一个家族
        fu[i]=i;
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        connect(x,y);//连接俩氢气
    }
    cin>>p;
    for(int i=0;i<p;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(find(x)==find(y))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}