刚刚学会并查集，背会了模板

觉得merge语句可以换种方式写

于是乎

修改了一下merge合并语句

改成了f[find(b)]=a

把b的祖先节点的父亲标记为a

常规操作是f[find(b)]=find(a)

把b的祖先节点的父亲标记为a的祖先节点

但是二者都是把两个集合合并起来

起到的效果也差不多啊

好像这样写没有问题啊

MLE10分

真是惊喜

为什么呢我不理解我不理解我不理解我不理解我不理解我不理解我不理解

如果说是因为f[find(b)]=a会使得树的深度增加

那么f[x]=的路径压缩时

不是都会把各自的祖先节点标记为自己的父亲吗

那时间复杂度和空间复杂度好像也不会炸啊

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10100],a,b,z;
int find(int x)
{
	if(f[x]==x)
	{
		return x;
	}
	return f[x]=find(f[x]);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>z>>a>>b;
		if(z==1)
		{
			f[find(b)]=a;
                        //改成正规操作就能AC
		}
		else if(find(a)==find(b))
		{
			cout<<"Y"<<endl;
		}
		else
		{
			cout<<"N"<<endl;
		}
	}
	return 0;
}

感谢各位神犇各位大佬的收看

能否为蒟蒻解答一下为什么MLE

感谢！！！

orz