86158615777a @ 2018-08-08 20:38:19
#include<bits/stdc++.h>
using namespace std;
int father[10001];
char result[200001];
int find(int);
void unionn(int ,int);
int main()
{
int n,m,i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
father[i]=i;
for(i=1;i<=m;i++)
{
int x,y,w;
scanf("%d%d%d",&w,&x,&y);
if(w==1){
int r1=find(x),r2=find(y);
if(r1!=r2)
unionn(r1,r2);
}
if(w==2)
{
int r1=find(x);
int r2=find(y);
if(r1!=r2) result[i]='N';
else result[i]='Y';
}
}
for(i=1;i<=m;i++)
if(result[i]=='Y'||result[i]=='N') cout<<result[i]<<endl;
}
int find(int x)
{
while(x!=father[x]) x=father[x];
return x;
}
void unionn(int x,int y)
{
father[y]=x;
}
by Viston @ 2018-08-08 20:40:03
看不出有什么毛病啊
by 马峰 @ 2018-08-08 20:43:54
您这应该是t了吧,没路径压缩
by 顾z @ 2018-08-08 20:48:44
那啥 ,为啥转成离线做呢
by 顾z @ 2018-08-08 20:51:58
提点意见
1路径压缩 2在线 (逃
by 顾z @ 2018-08-08 20:54:23
@ 86158615777a
by 86158615777a @ 2018-08-08 21:12:51
各位大佬,我知道原因了:1.数组开小了,少开了一个。2.我路径压缩用了非递归方法,而非递归方法超时了,而递归方法没超时。请教各位大佬,这是为什么?
by Papaya @ 2018-08-08 21:20:56
@86158615777a 数组小了吗?不见得 我把你的代码压缩之后就A了 (您可以把您的递归代码和非递归代码发出来看看)