并查集求助大神5re
查看原帖
并查集求助大神5re
1112575
with_my_moon楼主2024/5/25 18:23
using namespace std;

int n,m;
struct{
	int a;
	string s;
}p[100806];

int f(int g){
	if(p[g].a==g) return g;
	else p[g].a=f(p[g].a);
}

int fi(int g){
	if(p[g].a==g) return g;
	else fi(p[g].a);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>p[i].s;
		p[i].a=i;
	}
	string s1,s2;
	int x1,x2;
	for(int i=1;i<=m;i++){
		cin>>s1>>s2;
		for(int j=1;j<=n;j++){
			if(p[j].s==s1) x1=j;
			if(p[j].s==s2) x2=j;
		}
		if(f(x1)==f(x2)) continue;
		else if(f(x1)<f(x2)) p[x2].a=p[x1].a;
		else if(f(x1)>f(x2)) p[x1].a=p[x2].a;
	}
	int k;
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>s1>>s2;
		for(int j=1;j<=n;j++){
			if(p[j].s==s1) x1=j;
			if(p[j].s==s2) x2=j;
		}
		if(fi(x1)==fi(x2)) cout<<"Yes.";
		else cout<<"No.";
	}
	return 0;
}
2024/5/25 18:23
加载中...