题11

题11

题目

并查集中最核心的两个操作是：
(1) 查找, 查找两个元素是否属于同一个集合;
(2) 合并, 若两个元素不属于同一个集合, 且所在的两个集合互不相交, 则合并这两个集合. 假设初始长度为 的并查集，按 9 的顺序进行查找和合并操作, 最终并查集共有 ( ) 个集合.
A. 1
B. 2
C. 3
D. 4

分析

初始时, 各自成一个集合。查找 1-2 时,合并 和 ; 查找 3-4 时,合并 和 ; 查找 5-6 时,合并 和 ; 查找 7-8 时,合并 和 ; 查找 8-9 时,合并 和 ; 查找 1-8 时,合并 和 ; 查找 0-5 时,合并 和 ; 查找 1-9 时,它们属于同一个集合。最终的集合为 和 ,因此答案选择选项 。

解

C