【牛客网23803】DongDong认亲戚（并查集 + 字符串）

题目链接：DongDong认亲戚 (nowcoder.com)

在之前我写过一个并查集的题目，详见《【并查集】poj1611 – The Suspects – ErikTse Runtime》，这是一道用数字表示点的并查集模型，但是本题 DongDong认亲戚 是用字符串表示点的，其实换汤不换药，用一个map将字符串和编号联系起来就行了。

思路

并查集。

用一个map<string, int> s2i表示从string 指向 int。

我用了一下string的快速读入，让代码简洁了一些（疯狂压行），速度也更快。（cin读入真的挺慢的）

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
	int s = 0,w = 1;char c = gc();
	while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
inline string readString()
{
	string s;char c = gc();
	while(c == '\n' || c == '\r' || c == ' ')c = gc();
	while(c != '\n' && c != '\r' && c != ' '){s = s + c, c = gc();}
	return s ;
}
/*--------全局变量--------*/
const int maxn = 2e5 + 10;
map<string, int> s2i;
int pre[maxn];
/*--------自定义函数-------*/

inline int root(int x)
{
	int rx = x;
	while(pre[rx] != rx)rx = pre[rx];
	return pre[x] = rx;
}

signed main()
{
	int N = readInt(), M = readInt();
	for(int i = 1;i <= N; ++ i)pre[i] = s2i[readString()] = i;
	while(M --)
	{
		int op = readInt();
		if(op == 1)pre[root(s2i[readString()])] = root(s2i[readString()]);
		else if(op == 2)pr("%d\n", root(s2i[readString()]) == root(s2i[readString()]) ? 1 : 0);
	}
	
	return 0;
}