@[drewxa7](/user/1326527) 合并的时候特判一下,如果已经祖先相同就不合并直接跳过
如果不想这么改,那么参照题解,将祖先预处理为自己
by wangbinfeng @ 2024-03-29 17:21:39
@[wangbinfeng](/user/387009) 感谢解答,第一次用洛谷有点蜜汁自信以为是环境有什么问题,这里真的是疏忽了
by drewxa7 @ 2024-03-29 17:26:48
@[drewxa7](/user/1326527) 本地和luogu评测有时候还是有点区别的,你可以下载个NOI Linux虚拟机(比较麻烦,不推荐)或者用luogu在线IDE
by wangbinfeng @ 2024-03-29 17:27:52
@[wangbinfeng](/user/387009) ok谢谢,我以后会多用在线ide的
by drewxa7 @ 2024-03-29 17:29:45
考虑一条链,合并完得到这条链过后从下往上依次询问它与根的关系,由于你在 `find` 过程没有进行沿途所有节点的路径压缩,且 `merge` 过程也没有带启发式,那么最终的复杂度就会被卡到 $O(n^2)$ 从而得到 `TLE`
by kjhhjki @ 2024-03-29 19:47:29
纯C代码:
```c
#include<stdio.h>
int num[10010];
int arr[200010][3];
int find(int n)
{
int r=n;
while(r!=num[r])
r=num[r];
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx=find(x);
fy=find(y);
if(fx!=fy)
num[fy]=fx;
}
int main()
{
int N,M;
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
num[i]=i;
for(int i=0;i<M;i++)
scanf("%d%d%d",&arr[i][0],&arr[i][1],&arr[i][2]);
for(int i=0;i<M;i++)
{
if(arr[i][0]==1)
{
merge(arr[i][1],arr[i][2]);
}
else if(arr[i][0]==2)
{
if(find(arr[i][1])==find(arr[i][2]))
printf("Y\n");
else
printf("N\n");
}
}
return 0;
}
```
by bu_chi_suan @ 2024-03-31 14:45:08