专栏文章

题解：UVA10685 Nature

BBobi2014
UVA10685题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mins3ron
此快照首次捕获于
2025/12/02 07:26
3 个月前
此快照最后确认于
2025/12/02 07:26
3 个月前
查看原文
这是一道可癌的并查集 ++ unordered_map 题。

前置知识

思路

考虑先把字符串映射成数，可以使用 unordered_map，定义方式 unordered_map<string,int> mp，这样可以定义一个 unordered_map，unordered_map 的使用方式和数组差不多，直接 mp[str] 就可以直接修改和访问了。
接下来我们直接并查集操作，操作完后建一个 cntcnt 数组，枚举每个字符串，将它的祖先在 cntcnt 中加一。
最后扫一遍 cntcnt 数组，求出现次数最多的祖先的出现次数，也可以在枚举每个字符串时一起求。
时间复杂度 O(Qnv)O(Qnv)，vv 为微小常数。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[5005],cnt[5005];
unordered_map<string,int> mp;
void init(){
	for(int i = 1;i <= n;i ++){
		fa[i] = i;
	}
}
int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(true){
		cin >> n >> m;
		if(n == 0 and m == 0){
			break;
		}
		init();
		mp.clear();
		memset(cnt,0,sizeof(cnt));
		for(int i = 1;i <= n;i ++){
			string s;
			cin >> s;
			mp[s] = i;
		}
		for(int i = 1;i <= m;i ++){
			string a,b;
			cin >> a >> b;
			int x = find(mp[a]),y = find(mp[b]);
			if(x != y){
				fa[y] = x;
			}
		}
		int ans = 0;
		for(int i = 1;i <= n;i ++){
			cnt[find(i)] ++;
			ans = max(ans,cnt[find(i)]);
		}
		cout << ans << '\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...