题解

普通到不能再普通的并查集，只需要加一个记忆化就行。（老师版）
改前

#include<bits/stdc++.h>
using namespace std;
int fa[50005];
int get(int x){
    if(fa[x]==x)return x;
    return get(fa[x]);
}
void merge(int x,int y){
    fa[get(x)]=get(y);
}
int main(){
    int n,m,p;
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=n;i++)fa[i]=i;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(get(x)!=get(y))merge(x,y);
    }
    while(p--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(get(x)==get(y))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

改后

#include<bits/stdc++.h>
using namespace std;
int fa[50005];
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y){
    fa[get(x)]=get(y);
}
int main(){
    int n,m,p;
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=n;i++)fa[i]=i;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(get(x)!=get(y))merge(x,y);
    }
    while(p--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(get(x)==get(y))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}