问一下大佬,我这样算路径压缩吗?
查看原帖
问一下大佬,我这样算路径压缩吗?
352352
artalter楼主2020/9/20 18:51

我看其他讨论说不路径压缩会TLE,可我的代码却AC了

#include<iostream>
using namespace std;
struct s{
	int a[100001]={}; 
	void push(int x,int y)
	{
		if(a[x]==0&&a[y]==0)
		{
			a[x]=y;
			a[y]=y;
		 } else if(a[x]==0&&a[y]!=0)
		 {
		 	if(a[y]!=y)
		 		a[x]=find(y);
		 	else 
		 		a[x]=y;
		 }else if(a[y]==0&&a[x]!=0)
		 {
		 	if(a[x]!=x)
		 		a[y]=find(x);
		 	else 
		 		a[y]=x;
		 }else
		 {
		 	if(!bmp(x,y))
		 	{
		 		a[find(x)]=find(y);
			}
		 }
	}
	bool bmp(int x,int y)
	{
		if(x==y)return 1;
		if(a[x]==0||a[y]==0)return 0;
		if(find(x)==find(y))
		{
			return 1;
		}
		return 0;
	}
	int find(int x)
	{
		int ax=x;
		while(a[ax]!=ax)ax=a[ax];
		return ax;
	}
	void print(int x)
	{
		int ax=x;
		while(a[ax]!=ax)
		{
			cout<<ax<<"->";
			ax=a[ax];
		}
		cout<<ax;
		cout<<endl;
	}
};
int n,m,p;
int main()
{
	s a;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int z,x,y;
		cin>>z>>x>>y;
		if(z==1)
		{
			a.push(x,y);
		}
		if(z==2)
		{
			if(a.bmp(x,y))
			{
				cout<<"Y"<<endl;
			}else
			{
				cout<<"N"<<endl;
			}
		}
	}
	return 0;
}
2020/9/20 18:51
加载中...