要路径压缩,不然可能会卡到 $O(n)$。
把`find`改成这样就可以了。复杂度应该是 $O(\log n)$ 的。
```
int find(int k){
if(p[k]==k) return k;
return p[k]=find(p[k]);//把k到祖先这一条路径上的点的父亲都设为祖先。
}
by qlzx74lyc41 @ 2022-08-19 16:14:53
@[qlzx74lyc41](/user/575453) orzorz
by Iverson_ @ 2022-08-19 16:16:33
@[Iverson_](/user/602519) 要按秩合并,不然其他题可能会卡 $O(\log (n))$
把
```cpp
p[find(x)]=find(y);
```
改成
```cpp
{
int u=find(x);
int v=find(y);
if(sz[u]<sz[v]) swap(u,v);
p[v]=p[u];
sz[u]+=sz[v];
}
```
现在是 $O(a(n))$ 的了。
记得加上sz(秩/结点数)数组
by XHY20180718 @ 2022-08-23 23:14:41