洛谷题单指南-集合-P2814 家谱

原题链接：https://www.luogu.com.cn/problem/P2814

题意解读：已知多组父子关系，找某个人最早的祖先，并查集的应用。

解题思路：

由于存在真正的父子关系，所以在并查集合并的时候，要把p[x] = y中x设置为子，y设置为父，其余都是并查集的常规操作。

由于是计算姓名之间的父子关系，并查集可以用map<stirng, string> p来代替数组。

另外，由于需要对并查集进行初始化p[name] = name，因此先将所有数据读取存入map<string, vector<string>> h中，将所有要计算祖先的姓名存入

vector<string> q中，再遍历h进行集合合并，遍历q进行结果输出即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

map<string, vector<string>> h; //保存所有的父子关系
vector<string> q; //保存所有的要求祖先的人名
map<string, string> p; //并查集，由于父子关系是人名，因此用map来作并查集,p[name1] = name2表示name1的父亲是name2 

string find(string name)
{
    if(p[name] == name) return name;
    return p[name] = find(p[name]);
}

void merge(string son, string father)
{
    p[son] = father;
}

int main()
{
    char c;
    string father, son;
    while(cin >> c && c != '$')
    {
        if(c == '#') 
        {
            cin >> father;
            p[father] = father; //初始化并查集
        }
        if(c == '+')
        {
            cin >> son;
            h[father].push_back(son);
            p[son] = son; //初始化并查集
        } 
        if(c == '?')
        {
            cin >> son;
            q.push_back(son);
            p[son] = son;
        }
    }

    for(auto i : h)
    {
        for(auto j : i.second)
        {
            merge(j, i.first);
        }
    }

    for(auto i : q)
    {
        cout << i << " " << find(i) << endl;
    }

    return 0;
}