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

学术版

@[OrinLoong](/user/539345) 不一定,如果更改就会再次压缩。
by MLE_Automaton @ 2024-10-13 15:46:34


@[ChenXiJie2013](/user/928418) 我的意思是是不是每一次find完之后都压到了最优状态
by OrinLoong @ 2024-10-13 16:24:45


@[OrinLoong](/user/539345) 答案为每次 find 完后,在过程中经过的点深度都变为 2,与树根直接相连。以及我刚刚朗诵的是路径压缩的定义。建议你问问题之前先看看自己问题的定义(无恶意,纯建议)。
by rybp @ 2024-10-13 17:02:53


@[OrinLoong](/user/539345) 每次find完就直接跟根节点相连了啊
by MLE_Automaton @ 2024-10-13 18:04:24


不一定,举个简单的例子,如下: ``` 1 <= 2, 2 <= 3 find(2) = 1 ``` 注意到 3 仍然可压缩
by MarsCheng @ 2024-10-13 18:45:50


|