,需要两个整形参数(分别是节点的个数和连接节点的通道的数目),无返回值。(4) count 函数, 用来计算并查集含有集合的个数, 需要一个整形参数(节点的个数),返回一个整形值。(并查集含有集合的个数) (5)代码能实现并查集的创建,初始化,合并集合,查找节点所在集合和计算并查集中所含集合的数目。二. 解题思路: 1.创建两个数组 pre 和t,pre 数组下标用于表示节点的编号,数组内容表示节点的上级。 t用于标记独立块的根结点 2.首先定义出主函数的基本框架流程,用 while 和switch 函数来实习功能的选择 3. 由主函数中接收到参数 N、M给 chushihua 函数,然后函数用 for 循环给 pre 数组赋值, 使得并查集中每个节点都编好号而且每个节点自己成为一个集合, 然后用 mix 函数把需要连接的节点连起来,创建出一个新的并查集。 4. 由主函数中接受到参数 x给 Find 函数, 函数通过对 pre 数组的下标是否和数组的内容相等,从而判断该节点是否是根节点,找到后根节点的编号返回给主函数。 5. 由主函数接受到参数 x,y给 mix 函数, 函数通过 Find 函数分别找到 x和y 的根节点,然后通过把 y 所在集合的根节点的数组值改成 x 所在集合根节点的数组下标, 从而使得 x 所在集合的根节点成为 y 所在集合的根结点的上级。从而把两个集合合并。 6. 由主函数接受到参数 N给 count 函数,用 for 循环把各个节点遍历, 如果第 i 个节点是根节点,就把第 i 个节点所在的 t 数组的值赋值为 1 ,否则为 0 ,然后用 ans 标志 t 数组中 1 的个数。最后把 ans 返回给主函数。该代码用了线性表的数据结构。三. 调试分析: 1. 代码演示: 生成的并查集图为: 合并后并查集图为: 初始化后并查集的图: 合并后并查集的图:
全文预览
