P2814 家谱【map型的并查集】

题目

https://www.luogu.com.cn/problem/P2814

 思路

我们跨一使用string类型的map直接进行并查集！

注意这种形式的map的初始化！！

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
map<string, string>list;
string find(string x)
{
    if (x == list[x])return x;
    return list[x] = find(list[x]);
}
int main()
{
    string temp, father="";
    while (1)
    {
        cin >> temp;
        if (temp == "$")break;
        if (temp[0] == '#') { father = temp.substr(1, temp.length() - 1);  if(list[temp.substr(1, temp.length() - 1)]=="")list[temp.substr(1, temp.length() - 1)] = father;}
        if(temp[0]=='+') list[temp.substr(1, temp.length() - 1)] = father;
        if (temp[0] == '?') { cout << temp.substr(1, temp.length() - 1) <<' '<<find(temp.substr(1, temp.length() - 1)) << endl; }
    }


}