题目链接

捞

大体思路：以球为节点，把每个球连向盒子的第一个元素，查询时候查询第一个元素是哪个盒子的第一个元素。

$bot[i]$ 表示第 $i$ 个盒子的第一个元素。

$rec[i]$ 表示 $i$ 球是哪个盒子的第一个元素。

$fa[i]$ 表示 $i$ 的祖先，并查集数组。

$siz[i]$ 表示第 $i$ 个盒子里有多少个球。

操作1：$fa[[bot[y]]\gets bot[x]$，把 $y$ 盒子的第一个元素 连向 $x$ 盒子的第一个元素。并将 $y$ 盒子清空。

操作2：将 $k$ 连向 $bot[x]$。

操作3：输出 $rec[findroot(x)]$。

现在的状况是 WA+RE，不知道是思路假了，还是实现假了，真心求助大佬。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q,k,fa[N],bot[N],rec[N],siz[N];
int fr(int x){return x==fa[x]?x:fa[x]=fr(fa[x]);}
signed main()
{
	cin>>n>>q;k=n;
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;siz[i]=1;
		bot[i]=i;rec[i]=i;
	}
	while(q--)
	{
		int opt,x,y;cin>>opt>>x;
		if(opt==1)
		{
			cin>>y;
			if(siz[y]==0)continue;
			if(siz[x])fa[bot[y]]=bot[x],rec[bot[y]]=0;
			else rec[bot[y]]=x;
			siz[x]+=siz[y];siz[y]=0;bot[y]=0;
		}
		else if(opt==2)
		{
			k++;
			if(siz[x])fa[k]=bot[x];
			else
			{
				fa[k]=k;bot[x]=k;
				rec[k]=x;
			}
			siz[x]++;
		}
		else
		{
			cout<<rec[fr(x)]<<endl;
		}
	}
	return 0;
}