求助,开不开O2都RE,85pts
查看原帖
求助,开不开O2都RE,85pts
755293
vegetable_doggy楼主2023/11/9 19:18
#include<bits/stdc++.h>
#define itn int
#define ll long long
using namespace std;
const int N=1e5+10;
const int M=1e2;
int n,m,q;
int fa[N];
int tim;
ll ans;
string s1[N][5],s2[N][5];

map <string, int> mp;
int Find(int x){
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		s1[i][1].resize(M);
		s1[i][2].resize(M);
		scanf("%s %s",&s1[i][1][0],&s1[i][2][0]);
		if(mp[s1[i][1]]==0){
			mp[s1[i][1]]=++tim;
		}if(mp[s1[i][2]]==0){
			mp[s1[i][2]]=++tim;
		}
//		cout<<s1[i][1]<<"\n"<<s1[i][2];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		s2[i][1].resize(M);
		s2[i][2].resize(M);
		scanf("%s %s",&s2[i][1][0],&s2[i][2][0]);
		if(mp[s2[i][1]]==0){
			mp[s2[i][1]]=++tim;
		}if(mp[s2[i][2]]==0){
			mp[s2[i][2]]=++tim;
		}
	}
	cin>>q;
	for(int i=1;i<=tim;i++){
		fa[i]=i;
	}
	for(int i=1;i<=q;i++){
		string c,c1,c2;
		c.resize(M);c1.resize(M);c2.resize(M);
		scanf("%s %s %s",&c[0],&c1[0],&c2[0]);
//		cout<<c<<" "<<c1<<" "<<c2<<"\n";
		if(mp[c]==0){
			mp[c]=++tim;
			fa[tim]=tim;
		}if(mp[c1]==0){
			mp[c1]=++tim;
			fa[tim]=tim;
		}if(mp[c2]==0){
			mp[c2]=++tim;
			fa[tim]=tim;
		}
		int xx=Find(mp[c]);	
		int yy=Find(mp[c1]);	
		int zz=Find(mp[c2]);				
		fa[zz]=fa[yy]=xx;
	}
	for(int i=1;i<=n;i++){
		if(fa[ Find(mp[s1[i][1]]) ]!=fa[ Find(mp[s1[i][2]]) ] ){
			ans++;
		}
	}
	for(int i=1;i<=m;i++){
		if(fa[mp[s2[i][1]]]==fa[mp[s2[i][2]]]){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
2023/11/9 19:18
加载中...