路径压缩的并查集每次find后的结果都是不可再压缩的吗？

OrinLoong @ 2024-10-13 15:44:59

by MLE_Automaton @ 2024-10-13 15:46:34

@OrinLoong 不一定，如果更改就会再次压缩。

by OrinLoong @ 2024-10-13 16:24:45

@ChenXiJie2013 我的意思是是不是每一次find完之后都压到了最优状态

by rybp @ 2024-10-13 17:02:53

@OrinLoong 答案为每次 find 完后，在过程中经过的点深度都变为 2，与树根直接相连。以及我刚刚朗诵的是路径压缩的定义。建议你问问题之前先看看自己问题的定义（无恶意，纯建议）。

by MLE_Automaton @ 2024-10-13 18:04:24

@OrinLoong 每次find完就直接跟根节点相连了啊

by MarsCheng @ 2024-10-13 18:45:50

不一定，举个简单的例子，如下：

1 <= 2, 2 <= 3
find(2) = 1

注意到 3 仍然可压缩