洛谷 - 家谱 (字符串并查集)
程序员文章站
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;
}
}
上一篇: Bellman-Ford 求最长路
下一篇: 第二节课Matplotlib