2019徐州网络赛 - so easy

题目链接:so easy

一道哈希+并查集。

因为数字比较多，我们不能开数组并查集，但是询问次数不多，所以询问涉及的数字不多，我们哈希即可。然后哈希可以利用C++的 unordered_map。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
unordered_map<int,int> mp;
int n,q;
int find(int x){
	if(!mp[x])	return x;
	if(mp[x]==-1)	return -1;
	else return mp[x]=find(mp[x]);
}
signed main(){
	scanf("%d %d",&n,&q);	mp[n]=-1;
	while(q--){
		int z,x;	scanf("%d %d",&z,&x);
		if(z==1)	mp[x]=find(x+1);
		else	printf("%d\n",find(x));
	}
	return 0;
}