思路

用并查集找公共祖先，需要压缩路径。

int find(int x){
	if (x == fa[x])	return x;
	return fa[x] = find(fa[x]);
}

void merge(int x,int y){
	fa[find(y)] = find(x);
}

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20005,M = 1000005,Q = 1000005;
int a[N];
int find(int x){
	if (x == a[x])	return x;
	return a[x] = find(a[x]);
}
void merge(int x,int y){
	a[find(y)] = find(x);
}
int main(int argc, char **argv){
	for (int i = 0;i < N;i++)	a[i] = i;
	int n,m,q;
	cin >> n >> m;
	for (int i = 0;i < m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		merge(x,y);
	}
	cin >> q;
	for (int i = 0;i < q;i++){
		int c,d;
		scanf("%d %d",&c,&d);
		if(find(c) == find(d))	printf("Yes\n");
		else	printf("No\n");
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int MAX_A=2e4+10;
int d[MAX_A];
int find(int x){
    if(x==d[x]){
        return x;
    }
    return d[x]=find(d[x]);
}
void add(int x,int y){
    d[find(x)]=find(y);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=n;i++) d[i]=i;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        if(find(a)==find(b)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    
    return 0;
}

歹马： 注意：输入数据多，要用scanf和printf

#include<bits/stdc++.h>
using namespace std;
const int MAX_A=2e4+10;
int d[MAX_A];
int find(int x){
    if(x==d[x]){
        return x;
    }
    return d[x]=find(d[x]);
}
void add(int x,int y){
    d[find(x)]=find(y);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=n;i++) d[i]=i;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        if(find(a)==find(b)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    
    return 0;
}

思路

不要使用没解绑的cin,cout

不然,81TLE

代码

#include<iostream>
using namespace std;
int n,m,q;
int fa[114514];
int find(int x)//找祖先
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
void hb(int x,int y)//合并
{
    fa[find(x)]=find(y);
}
int main()
{
    scanf("%i%i",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;//初始化
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%i%i",&u,&v);
        hb(u,v);//合并
    }
    cin>>q;
    while(q--)
    {
        int u,v;
        scanf("%i%i",&u,&v);
        if(find(u)==find(v))//查看祖先是否相同
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;//完结散花
}

using namespace std;
int f[20001],n,m;
int find(int x){
if(f[x]==x){
return x;
}
else{
f[x]=find(f[x]);
return f[x];
}
}
void merge(int x,int y){
f[find(x)]=find(y);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
merge(a,b);
}
int q;
cin>>q;
for(int i=1;i<=q;i++){
int c,d;
cin>>c>>d;
if(find(c)==find(d)){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
}