求助!找不到问题TAT
查看原帖
求助!找不到问题TAT
465246
GTY_very_like_it楼主2022/11/14 20:51
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;

struct node{
	int x,y;
};
node a[N][2];

map<string,int> maps;

int n,m,q;
int cnt;
int ans;
int f[N];

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

void merge(int x, int y){
	x = find(x);
	y = find(y);
	if(x != y) f[x] = y;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		string s1,s2;
		cin >> s1 >> s2;
		if(!maps[s1]) maps[s1] = ++cnt;
		if(!maps[s2]) maps[s2] = ++cnt;
		a[i][0].x = maps[s1];
		a[i][0].y = maps[s2];
	}
	
	cin >> m;
	for(int i = 1; i <= m; i++){
		string s1,s2;
		cin >> s1 >> s2;
		if(!maps[s1]) maps[s1] = ++cnt;
		if(!maps[s2]) maps[s2] = ++cnt;
		a[i][1].x = maps[s1];
		a[i][1].y = maps[s2];
	}
	
    for(int i = 1; i <= cnt; i++) f[i] = i;
	
	cin >> q;
	for(int i = 1; i <= q; i++){
		string s1,s2,s3;
		cin >> s1 >> s2 >> s3;
		int x = maps[s1];
		int y = maps[s2];
		int z = maps[s3];
		merge(x,y);
		merge(y,z);
	}
	
	for(int i = 1; i <= n; i++){
		int x = a[i][0].x;
		int y = a[i][0].y;
		if(find(x) != find(y)) ans++;
	}
	for(int i = 1; i <= m; i++){
		int x = a[i][1].x;
		int y = a[i][1].y;
		if(find(x) == find(y)) ans++;
	}
	
	cout << ans;



	return 0;
}
2022/11/14 20:51
加载中...