冰茶几求助(T)
查看原帖
冰茶几求助(T)
1353330
K_J_M楼主2024/7/18 22:13
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int x,y,g;
string s1[N],s2[N];
string a[N],b[N],c[N];
map<string,string>f1;
map<string,string>f2; 
map<string,string>f3;
map<string,int>siz1;
map<string,int>siz2;
map<string,int>siz3; 
string find1(string x){
	if(f1[x]==x) return x;
	return f1[x]=find1(f1[x]);
}
string find2(string x){
	if(f2[x]==x) return x;
	return f2[x]=find2(f2[x]);
}
string find(string x){
	if(f3[x]==x) return x;
	return f3[x]=find(f3[x]);
}
void Union1(string x,string y){
	string fx=find1(x),fy=find1(y);
	if(siz1[fx]<siz1[fy]){
		f1[fx]=fy;
	}else{
		if(siz1[fx]>siz1[fy]){
			f1[fy]=fx;
		}else{
			f1[fx]=fy;
			siz1[fy]++;
		}
	}
}
void Union2(string x,string y){
	string fx=find2(x),fy=find2(y);
	if(siz2[fx]<siz2[fy]){
		f2[fx]=fy;
	}else{
		if(siz2[fx]>siz2[fy]){
			f2[fy]=fx;
		}else{
			f2[fx]=fy;
			siz2[fy]++;
		}
	}
}
void Union3(string x,string y){
	string fx=find(x),fy=find(y);
	if(siz3[fx]<siz3[fy]){
		f3[fx]=fy;
	}else{
		if(siz3[fx]>siz3[fy]){
			f3[fy]=fx;
		}else{
			f3[fx]=fy;
			siz3[fy]++;
		}
	}
}
int main(){
	cin>>x;
	for(int i=1;i<=x;i++){
		cin>>s1[i]>>s2[i];
		f1[s1[i]]=s1[i];
		f1[s2[i]]=s2[i];
		siz1[s1[i]]++;
		siz1[s2[i]]++;
	}
	for(int i=1;i<=x;i++){
		Union1(s1[i],s2[i]);
	}
	cin>>y;
	for(int i=1;i<=y;i++){
		cin>>s1[x+i]>>s2[x+i];
		f2[s1[x+i]]=s1[x+i];
		f2[s2[x+i]]=s2[x+i];
		siz2[s1[x+i]]++;
		siz2[s2[x+i]]++;
	}
	for(int i=1;i<=y;i++){
		Union2(s1[i+x],s2[i+x]);
	}
	cin>>g;
	for(int i=1;i<=g;i++){
		cin>>a[i]>>b[i]>>c[i];
		f3[a[i]]=a[i];
		f3[b[i]]=b[i];
		f3[c[i]]=c[i];
		siz3[a[i]]++;
		siz3[b[i]]++;
		siz3[c[i]]++;
	}
	for(int i=1;i<=g;i++){
		Union3(a[i],b[i]);
		Union3(a[i],c[i]);
	}
	int ans=0;
	for(int i=1;i<=x;i++){
		if(find(s1[i])!=find(s2[i])){
			ans++;
		}
	}
	for(int i=x+1;i<=x+y;i++){
		if(find(s1[i])==find(s2[i])){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
2024/7/18 22:13
加载中...