欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 - 家谱 (字符串并查集)

程序员文章站 2022-05-22 10:36:03
...

题目链接
题目:
洛谷 - 家谱 (字符串并查集)
洛谷 - 家谱 (字符串并查集)
思路:
就是个赤裸裸的并查集(就是集合的划分),但是这个是字符串的并查集(我就是不会这种操作。。。随便取的名字),以前我只做过数字的并查集,字符串的还是第一次。

详情看代码注释

#include <bits/stdc++.h>
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 5e4 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
map<string,string> mp;
string Find(string s)
{
    if(mp[s] == s) return s;
    else return mp[s] = Find(mp[s]);
}//并查集
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    char c;
    cin >> c;//先输入一个字符,为了方便判断是插入元素,还是查找元素,还是结束
    string s,a;
    while(c != '$')
    {
        cin >> s;
        if(c == '#') {a = s;if(mp[s] == "") mp[s] = s;}//如果为'#'肯定为父亲节点,让a记录,mp中如果s没有被记录,则记录一下
        else if(c == '+') mp[s] = a;//如果为‘+’,这个s一定是a的儿子,记录
        else cout << s << " " << Find(s) << endl;//如果为‘?’,则为查找操作
        cin >> c;
    }
}
相关标签: 洛谷 板子代码