陈皮宇宙总统 @ 2017-08-08 16:13:37
#include<iostream>
#include<cstdio>
#define maxn 5001
using namespace std;
int fa[maxn];
int m,n,x,y,z;
int find(int x)
{
if(fa[x]!=x)return find(fa[x]);
else return x;
}
void unio(int r1,int r2)
{
fa[r2]=r1;
}
void pan(int x,int y)
{
if(find(x)==find(y))cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
cin>>z>>x>>y;
if (z==2)pan(x,y);
else if (z==1)
{
int r1=find(x);
int r2=find(y);
if (r1!=r2)unio(r1,r2);
}
}
return 0;
}
by 陈皮宇宙总统 @ 2017-08-08 16:34:07
数组改大以后就是TLE了。。。
by Neo_Kylinson @ 2017-08-17 21:46:41
+1s
by 饮溪 @ 2017-08-21 19:48:12
没有写路径压缩
by 饮溪 @ 2017-08-21 19:49:32
@陈皮宇宙总统
int find(int x)
{
if (fa[x]==x) return x;
return (fa[x]=find(fa[x]));
}
by 陈皮宇宙总统 @ 2017-08-21 20:30:59
感谢大神