题解：UVA10685 Nature

Bobi2014 · 2025-09-27 11:44:26 · 题解

这是一道可癌的并查集 + unordered_map 题。

前置知识

• 并查集

思路

考虑先把字符串映射成数，可以使用 unordered_map，定义方式 unordered_map<string,int> mp，这样可以定义一个 unordered_map，unordered_map 的使用方式和数组差不多，直接 mp[str] 就可以直接修改和访问了。

接下来我们直接并查集操作，操作完后建一个 cnt 数组，枚举每个字符串，将它的祖先在 cnt 中加一。

最后扫一遍 cnt 数组，求出现次数最多的祖先的出现次数，也可以在枚举每个字符串时一起求。

时间复杂度 O(Qnv)，v 为微小常数。

Code

#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;
}