求助,并查集思路一直卡65分
查看原帖
求助,并查集思路一直卡65分
924673
Akua楼主2024/1/28 20:13
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int f[maxn];


struct node{
	string l,r;
};

int find(int x){
	if(f[x] != x) return f[x] = find(f[x]);
	return f[x];
}

void join(int x,int y){
	int fx = find(x),fy = find(y);
	if(fx != fy){
		f[fx] = fy;
	}
}
map<int,string> mp;
map<string,int> mp2;

vector<node> all,re;
signed main (){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	int x,loc = 0;
	
	cin >> x;
	
	while(x--){
		string s1,s2;
		cin >> s1 >> s2;
		if(mp2[s1] == 0){
			mp2[s1] = ++ loc;
			mp[loc] = s1;
		}
		if(mp2[s2] == 0){
			mp2[s2] = ++ loc;
			mp[loc] = s2;
		}
		all.push_back({s1,s2});
	}
	
	int y;
	cin >> y;
	while(y--){
		string s1,s2;
		cin >> s1 >> s2;
		if(mp2[s1] == 0){
			mp2[s1] = ++ loc;
			mp[loc] = s1;
		}
		if(mp2[s2] == 0){
			mp2[s2] = ++ loc;
			mp[loc] = s2;
		}
		re.push_back({s1,s2});
	}
	
	for(int i = 1; i <= loc; i++) f[i] = i;
	int g;
	cin >> g;
	while(g--){
		string s1,s2,s3;
		cin >> s1 >> s2 >> s3;
		join(mp2[s1],mp2[s2]);
		join(mp2[s1],mp2[s3]);
		join(mp2[s3],mp2[s2]);
	}
	
	int ans = 0;
	int len = all.size();
	for(int i = 0; i < len ;i++){
		int l = mp2[all[i].l],r = mp2[all[i].r];
		if(find(l) != find(r)) ans++;
	}
	
	len = re.size();
	for(int i = 0; i < len; i++){
		int l = mp2[re[i].l],r = mp2[re[i].r];
		if(find(l) == find(r)) ans++;
	}
	
	cout << ans;
	return 0;
}
2024/1/28 20:13
加载中...