洛谷P2814 家谱

题目传送门

洛谷 P2814 家谱

思路

水的典型的并查集题目，但在建立关系时需要有一定的思考，因为名字都是字符串，所以这里采用了map以建立名字和名字之间的关系

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<string, string> persons;

string s, t, p;

string zuisu(string x) {//溯源函数
    if (persons[x] == x) {
        return x;
    }
    return persons[x] = zuisu(persons[x]);//找到后更新关系，以后就不用一代一代的查找了
}

void f(string x, string y) {//将x和y建立关系
    string xx = zuisu(x);
    if (xx != y)
        persons[y] = xx;
}

int main() {
    while (cin >> s && s != "$") {
        if (s[0] == '#') {
            t = s.substr(1);//从第二个元素开始将名字保存在变量t中
            if (persons[t] == "") {
                persons[t] = t;
            }
        } else if (s[0] == '+') {
            p = s.substr(1);
            f(t, p);//将t和p建立关系
        } else if (s[0] == '?') {
            p = s.substr(1);
            zuisu(p);
            cout << p << " " << persons[p] << endl;
        }
    }
    return 0;
}