@[peterwuyihong](/user/100325) @[7KByte](/user/119261) @[monstersqwq](/user/191868)
昨晚仔细一想，基于全随机合并的证明似乎都是不对的。
完全随机的并查集深度是可能被卡到 O(n) 的。考虑不断 merge(1,2),merge(1,3)...merge(1,n)，每次 1 号点的期望深度增加 $\frac 1 2$，最终 1 号点的期望深度为 $\frac n2$。
### 我有个靠谱证明：
对于一个 x，定义 $f_i$ 为其根的权值，考虑每次拿来一个 y 来跟他合并。我们相当于让：
$f_x\gets \min(f_x,f_y)$
所以就相当于说，每个节点初始有个值 $f_i$，合并就可以看成一个随机序列 $g_i$。第 j 次合并我们把 $f_i$ 对 $g_j$ 取 min，如果取 min 成功则 i 的深度+1，否则深度不变。
而有一个结论，似乎就是随机序列的前缀 max 期望长度只有 log 量级。也即成功取 min 的次数也是 log 量级。
### 卡全随机合并示例代码（1的深度会达到4900左右）：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int NR = 1e4 + 5;
int fa[NR];
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
void mrg(int x, int y) {
x = find(x), y = find(y);
if (rand() & 1) swap(x, y);
fa[y] = x;
}
int main() {
int n=1e4;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) mrg(1, i);
int x = 1, cnt = 0;
while (x != fa[x]) x = fa[x], ++cnt;
cout << cnt;
return 0;
}
```
by ethan_zhou @ 2022-02-11 08:49:58
@[ethan_zhou](/user/124740) 哦你这是随机合并啊，那我是合并随机/迷惑
差不多这样写
```python
rnd=[random.random() for i in range(n)]
fa=[i for i in range(n)]
def get(x):
if x==fa[x]:
return x
return get(fa[x])
def merge(x,y):
x,y=get(x),get(y)
if rnd[x]>rnd[y]:
fa[x]=y
else:
fa[y]=x
```
by peterwuyihong @ 2022-02-11 11:36:29
@[peterwuyihong](/user/100325) 我的写法是和你一样的。。我是说那些人的证明不对（他们证明是基于随机合并的）
by ethan_zhou @ 2022-02-11 12:34:53