LZOI2121 题解

__cheems__ · 2023-07-13 10:15:38 · 个人记录

题意

给出部分人的父亲，对于每个被访问的人，求他们的祖先。

思路

并查集的模板，只需实现查祖先的功能。

#include<bits/stdc++.h>
using namespace std;
char c;
string s,fr;
map<string,string> fa;
string find(string x){
    if(fa[x]==x) return x;
    return find(fa[x]); 
}
int main(){
    while(cin>>c){
        if(c=='$') break;
        cin>>s;
        if(c=='#'){
            fr=s;
            if(fa[s]=="") fa[s]=s;
        }
        else if(c=='+'){
            fa[s]=fr;
        }
        else if(c=='?'){
            cout<<s<<" "<<find(s)<<endl;
        }
    }
    return 0;
}