求助,并查集
查看原帖
求助,并查集
540956
douweiqi楼主2023/11/5 22:39
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e6+10;
const int M=1e3+10;
int f[N];
map<string,int> ma;
int find(int k){
	if(f[k]==k) return f[k];
	f[k]=find(f[k]);
	return f[k];
}
void Hb(int x,int y){//x排到y后 
	int xx=find(x);
	int yy=find(y);
	f[xx]=yy;
}
int x,y,g;
int cnt=0;
int findb(string k){
	if(ma[k]==0){
		cnt++; 
		f[cnt]=cnt;
		ma[k]=cnt;
	}
	return ma[k];
}
struct classma{
	int x,y;
}can[N],cant[N];
int main(){
	cin>>x;
	string a,b;
	for(int i=1;i<=x;i++){
		cin>>a>>b;
		can[i].x=findb(a);
		can[i].y=findb(b);
	}
	cin>>y;
	for(int i=1;i<=y;i++){
		cin>>a>>b;
		cant[i].x=findb(a);
		cant[i].y=findb(b); 
	}
	cin>>g;
	int ans=0;
	string c;
	for(int i=1;i<=g;i++){
		cin>>a>>b>>c;
		Hb(findb(a),findb(b));
		Hb(findb(b),findb(c));
	}
	for(int i=1;i<=x;i++){
		if(find(can[i].x)!=find(can[i].y)) ans++;
	}
	for(int i=1;i<=y;i++){
		if(find(cant[i].x)==find(cant[i].y)) ans++;
	}
	cout<<ans;
	return 0;
}

2023/11/5 22:39
加载中...