下列关于并查集的说法中，正确的是（ ）（注：本题涉及图的考点）。

A. 并查集不能检测图中是否存在环路 B. 通过路径优化后的并查集在最坏情况下的高度仍是 O(n) C. Find 操作返回集合中元素个数的相反数，它用来作为某个集合的标志 D. Union 操作时可根据当前集合的规模，将小集合合并到大集合中

[tag_link]

正确答案：D

推导

D 是按规模合并：把较小树的根挂到较大树的根下。A 错在并查集可判无向图加边是否成环；B 忽略路径压缩；C 错在 Find 返回代表元（根），根位置的负值才可记录规模。

易错点

要区分 Find 的返回值与 parent[root] 的负值语义；二者不是同一概念。