C++ 中通过连接非互质节点形成的图的最大连通分量大小

在本文中，我们将讨论如何找到通过 C++ 连接非互质节点所形成的图中最大连通分量的问题。图的节点通过边连接在一起。图的元素是构成图节点的子集值。一个图 G由一组a[]值组成。这些值来自构成图节点的组件集。互质数是除 1 以外没有其他最大公因数 (GCF) 的数。因此，它们在任何其他因数中都不常见。这里，使用了两种不同的技术。

现在，在一个由 N 个节点组成的图中，我们确定与所有节点关联的值 A。需要通过使用非互质受限节点之间的连接来计算图的最大连通分量。如果两个节点 U 和 V 是非互质的，则它们之间存在一条边。这意味着如果 A[U] 和 A[V] 的最大公因数大于 1。

示例

输入 {12,4,5,45,12,5,11,49}

输出 6

方法 1：朴素方法

我们可以从所有节点对的集合开始，然后验证它们是否互质。如果它们都不是互质数，我们将决定如何处理它们。接下来，我们将通过深度优先搜索来查找最大连通分量的大小。

以下代码描述了实现。

示例

输出

7

说明

• 该代码编写了一个名为dfs_search的函数，用于对图执行深度优先搜索。
• 在此示例中，dfs_search函数最初对起始节点进行操作，将其标记为已访问，并递归搜索未访问的邻居。
• maxComponentLength函数根据数字数组实现图，其中非互质的数字作为边添加。该函数从一个名为 visited 的数组开始，用于跟踪已访问的节点，并使用 DFS 查找最大连通分量的长度。
• 主函数创建一个数组，为其分配数据，并调用maximumComponentLength来发现最长连通分量的长度并打印出来。

方法 2：高效方法

如果两个数字有共同的除数，那么它们就是非互质的。因此，最短路径将根据节点值的质因数分解来构建。

质因数分解可以通过应用埃拉托斯特尼筛法正确完成。相邻节点将使用不相交集数据结构（秩增加和路径压缩）进行分组。

数据的存储遵循以下原则。

• p[i] <- 表示节点 i 的父节点。
• size[i] 表示 i 的级别。
• id(p) -> 表示数字 p 是第一个作为元素 A[i] 的因数出现的。

我们将每个节点值分解为质数，并将这些质数存储在集合 S中。访问 S 的每个元素。如果我们第一次看到其中一个质数作为某个数字的因数（id[p] 为零），则通过当前索引指示该质数。如果 id[p] 已被标记，则简单地将节点与id[p]的节点合并。以下示例是一种高效的方法。

示例

输出

7

说明

• 在此示例中，代码设置了一个名为 small_factor 的数组，其中包含不超过 100,004 的数字的最小质因数。它将用于质因数分解。
• sieve_Method函数使用埃拉托斯特尼筛法算法填充 small_factor 数组中的值。它为每个数字筛选出最小质数。
• fact_number函数查找数字 num 的质因数并将它们放入集合中。
• 代码将数组定义为 id、parm 和 sizeVal，以存储组件信息。Ip 指的是列表中质因数的初始位置。parm 变量保存组件的父节点，sizeVal 保存组件的大小。
• rootNode函数负责根据并查集算法查找组件的根。它使用路径压缩来加速后续搜索。
• mergeNodes方法通过更改它们的根节点和大小来合并两个组件。
• maxComponent函数获取输入并计算主要组件。它初始化对象，调用 sieve 方法，并遍历输入数组。
• 它计算输入数组中每个元素的质因数，并将它们保存在一个名为 sset 的集合中。它还决定质因数是否以前见过。
• 每当第一次出现质因数时 (id[it] == 0)，将当前索引加一的值设置为 id[it]。否则，它会将当前元素与 id[it] 元素组合起来。
• 遍历所有数字后，该函数通过循环遍历它们并将值存储在变量中来查找最大组件大小。
• 最后，主函数在空间中输入一个数字数组，现在调用maxComponent，它将找到最大组件大小并显示它。