RE,求调
查看原帖
RE,求调
751073
wuxiyi楼主2023/6/13 21:15
#include<bits/stdc++.h>
using namespace std;

unordered_map<string,int>mp;
int cnt=0;
int mp_find(string s){
	if (mp.find(s)==mp.end())	return mp[s]=++cnt;
	else	return mp[s];
}

int a1[114514],a2[114514],a3[114514],a4[114514];
int cnt1=0,cnt2=0;
//union find
int f[123456];
int si_ze=114514;
void init(){
	for (int i=0;i<=si_ze;i++)	f[i]=i;
	mp.clear();
}
int find(int x){
	if (f[x]!=x)	return f[x]=find(f[x]);
	return f[x];
}
bool insame(int x,int y){
	if (f[find(x)]==f[find(y)])	return 1;
	else	return 0;
}
void connect(int x,int y){
	if (!insame(x,y))	f[find(y)]=find(x);
}

int main(){
	init();
	
	int x,y,g;
	
	scanf("%d",&x);
	for (int i=1;i<=x;i++){
		string a,b;
		cin>>a>>b;
		int c=mp_find(a),d=mp_find(b);
		a1[++cnt1]=c;
		a2[cnt1]=d;
	}
	
	scanf("%d",&y);
	for (int i=1;i<=y;i++){
		string a,b;
		cin>>a>>b;
		int c=mp_find(a),d=mp_find(b);
		a3[++cnt2]=c;
		a4[cnt2]=d;
	}
	
	scanf("%d",&g);
	for (int i=1;i<=g;i++){
		string a,b,c;
		cin>>a>>b>>c;
		int d=mp_find(a),e=mp_find(b),f=mp_find(c);
		connect(d,e);
		connect(e,f);
	}
	
	int ans=0;
	for (int i=1;i<=x;i++){
		if (!insame(a1[i],a2[i]))	ans++;
	}
	for (int i=1;i<=y;i++){
		if (insame(a3[i],a4[i]))	ans++;
	}
	
	printf("%d\n",ans);
	return 0;
}
2023/6/13 21:15
加载中...