P2814 家谱 题解

Dijkstra_zyl · 2025-11-02 23:23:54 · 题解

P2814 家谱 题解

比较有意思的并查集

#include <iostream>//可以用map将自己和祖先联系在一起 并查集
using namespace std;
#include <map>
map<string,string> root;
string find(string x){
    if(x == root[x]) return root[x];
    else return root[x] = find(root[x]);
}
int main(){
    string name,father_name;
    char ch; cin >> ch;
    while(ch != '$'){
        cin >> name;
        if(ch == '#'){
            father_name = name;
            if(root[name] == "") root[name] = name;//如果没有祖先 指向自己 
        }else if(ch == '+') root[name] = father_name;
        else //询问 
            cout << name << " " << find(name) << '\n';
        cin >> ch;
    }
    return 0;
}