初始有 10 个单元素集合（0～9），依次对 1-2、3-4、5-6、7-8、8-9、1-8、0-5、1-9 执行查找与合并，最终并查集中有多少个集合？

A. 1 B. 2 C. 3 D. 4

[tag_link]

正确答案：C

推导

有效合并后得到 {0,5,6}、{1,2,7,8,9}、{3,4} 三个集合；最后一次 1-9 的两元素已同集，不再减少集合数，故选 C。

易错点

只有两个根不同时 Union 才使集合数减 1；不能把每条操作都机械计为一次有效合并。