题12
题目
下列关于并查集的说法中, 正确的是 ( ) (注, 本题涉及图的考点).
A. 并查集不能检测图中是否存在环路的问题
B. 通过路径优化后的并查集在最坏情况下的高度仍是
C. Find 操作返回集合中元素个数的相反数, 它用来作为某个集合的标志
D. 并查集基于树的双亲表示法
分析
依次探测图的各条边, 用并查集检查该边依附的两个顶点是否已属于同一集合 (两个顶点的根结点是否相同)。若是, 则说明图中存在环路, A 错误。
经过路径优化后, 并查集在最坏情况下的高度远小于
Find 操作总返回当前根结点作为集合的标志,
解
D