UVA11503 Virtual Friends 题解

jianhe · 2023-09-01 19:57:00 · 题解

UVA11503 Virtual Friends 题解

算法：并查集+哈希

字符串怎么处理呢？ 可以用哈希来解决，用 unordered_map 来存储每一个字符串所对应的数值。之后就可以用并查集来做啦~。（之所以不用 map ，是因为 map 的常数比较大，里面的数据都是自动排序的，而 unordered_map 不会自动排序，常数略小。）

并查集不会的同志请做 P3367

此外，还有不少细节要注意。因为有多组数据，所以不要忘记每次循环都要初始化。初始化时，还要注意每次读入是两个人名，所以记得数组要开两倍。

上代码：

//UVA11503 Virtual Friends 题解 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+10;//开两倍不要忘了 
ll T,n,fa[N],sz[N],tot;
string x,y;
unordered_map<string,ll> p;
void jian(){
    //注意，i<=n*2，要*2哦 
    for(int i=0;i<=n*2;i++) fa[i]=i,sz[i]=1;
    return;
}
ll getfa(ll x){
    // fa=getfa(fa[x]) 用路径压缩，节省时间复杂度 
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void hebing(ll x,ll y){
    ll fx=getfa(x),fy=getfa(y);
    if(fx!=fy){//若 x 和 y 本身就是朋友，不需要再合并了 
        if(sz[fx]>sz[fy]) swap(fx,fy);
        fa[fx]=fy,sz[fy]+=sz[fx];//启发式合并，合并在短的一边，优化时间复杂度 
    }
}
ll size(ll x){
    return sz[getfa(x)];
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        p.clear(),tot=0,jian();//初始化 
        while(n--){
            cin>>x>>y;
            if(p.find(x)==p.end()) p[x]=++tot;//用 p 记录字符串所对应的数值 
            if(p.find(y)==p.end()) p[y]=++tot;
            hebing(p[x],p[y]);
            cout<<size(p[x])<<"\n";
        }
    }
    return 0;
}