极客笔记C++ 通过连接非互质节点形成的图中的最大分量大小
在本教程中，我们讨论通过C++连接非互质节点生成的图中寻找最大分量大小的问题。图由通过边连接的节点组成。图的分量是形成节点的值的子集。有一个数组a []形成图G。图的分量是形成节点的值的子集。非互质数是指除了1之外有最大公约数（HCF）的数，也就是说它们有其他公共因数。我们使用两种不同的方法解决本教程中的问题陈述。
演示1
Arr[] = {12, 15, 18, 21, 24, 30}
输出结果
6
说明
在上述示例中，输入数组的元素为{2, 15, 18, 21, 24, 30}。非互质节点的可能配对有(12, 15), (12, 18), (12, 24), (12, 30), (15, 18), (15, 21), (15, 24), (15, 30), (18, 21), (18, 24), (18, 30), (21, 24), (21, 30)和(24, 30)。
这些配对因为它们的最大公因数不是1而不是互质的。
考虑其中一个配对(12, 15)，其因数为2, 3, 5。
通过观察这些配对，最大的组件大小为6，它们是(12, 15, 18, 21, 24, 30)。
演示 2
Arr[] = {2, 4, 3, 9}
输出
2
解释
在上面的输入数组中，可以被视为非互质元素的组件是(2,4)和(3, 6)。因此，最大组件的大小为2。
C++库函数
语法
vector:
它是C++中的动态数组。与基本数组相比，它提供了高效的数组操作。
vector<data_type> vector_name;
push_back（）： 它是C++库中<vector>头文件中的预定义函数。它用于在向量的末尾插入或推送元素。
vector_name.push_back(value);
auto： auto是C++中的关键字，用于自动将数据类型赋给变量。它是在编译时自动声明变量的类型。
auto variable_name;
set（集合）： 它是C++中的一个容器，用于收集不重复的元素。 集合中的所有元素都是排序的。
set<data_type> set_name;
max(): 它在C++库的<algorithm>头文件中定义。它返回参数中的最大值。要找到最大值，需要两个参数。
max(value1, value2);
算法
- 初始化一个元素数组。
-
迭代所有非互质的可能节点对。
-
连接所有这些非互质的节点以形成图。
-
使用深度优先搜索找到最大的组件大小。
-
打印最大的组件大小。
示例1
在这个方法中，我们使用深度优先搜索来在形成图之后找到最大的组件大小。图中包含了非互质的节点。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int depthFirstSearch(int v, vector<int>* ad, int vnode[]) {
vnode[v] = 1;
int compSize = 1;
for (auto it : ad[v]) {
if (!vnode[it]) {
compSize += depthFirstSearch(it, ad, vnode);
}
}
return compSize;
}
int maxComponentSize(int a[], int num) {
vector<int> ad[num];
for (int x = 0; x < num; x++) {
for (int y = x + 1; y < num; y++) {
if (__gcd(a[x], a[y]) > 1) {
ad[x].push_back(y); // Constructing undirected graph
ad[y].push_back(x);
}
}
}
int result = 0;
int vnode[num];
for (int l = 0; l < num; l++) {
vnode[l] = 0;
}
for (int x = 0; x > num; x++) {
if (!vnode[x]) {
result = max(result, depthFirstSearch(x, ad, vnode));
}
}
return result;
}
int main() {
int num = 6;
int a[] = { 2, 4, 8, 3, 9, 15 };
cout << "The maximum component size in the graph is: " << maxComponentSize(a, num) << endl;
return 0;
}
输出
The maximum component size in the graph is: 0
示例 2
在这个C++实现中，我们不是通过遍历所有的数组元素来找到每对节点的最大公约数，而是将所有的节点值进行质因数分解，并将它们与公共因数合并。使用埃拉托斯特尼筛法（一种在给定范围内找质数的算法）进行质因数分解。
#include <bits/stdc++.h>
using namespace std;
//defining value of prime factor
int primefactor[100005];
// implementing Sieve of Eratosthenes algorithm
void sieveOfE()
{
for (int x = 2; x < 100005; x++)
{
if (primefactor[x] == 0)
{
primefactor[x] = x;
for (int y = 2 * x; y < 100005; y += x)
{
if (primefactor[y] == 0)
primefactor[y] = x;
}
}
}
}
// using set to store the prime factors
void primeFactorization(int m, set<int>& st)
{
while (m > 1)
{
int a = primefactor[m];
st.insert(a);
while (m % a == 0)
m /= a;
}
}
// Disjoint set data structure to group nodes
int id1[100005];
int p[100005];
int contsize[100005];
int rootComp(int x)
{
if (p[x] == x)
return x;
else
return p[x] = rootComp(p[x]);
}
// grouping components
void mergeComp(int c, int d)
{
// finding roots
int i = rootComp(c);
int j = rootComp(d);
if (i == j)
return;
if (contsize[i] > contsize[j])
swap(i, j);
p[i] = j;
contsize[j] += contsize[i];
}
// finding maximum component size
int maxComponentsize(int arr[], int num)
{
for (int x = 0; x < 100005; x++)
{
p[x] = x;
contsize[x] = 1;
}
sieveOfE();
for (int x = 0; x < num; x++)
{
set<int> st;
primeFactorization(arr[x], st);
for (auto it : st)
{
if (id1[it] == 0)
id1[it] = x + 1;
else
mergeComp(x + 1, id1[it]);
}
}
int result = 0;
//using max function for container size
for (int x = 0; x < num; x++)
result = max(result, contsize[x]);
return result;
}
// code Controller
int main()
{
int num = 8;
int arr[] = { 2, 6, 3, 7, 12, 4, 21, 36 };
cout << maxComponentsize(arr, num);
return 0;
}
输出
8
结论
我们已经到达这个使用C++来找到通过连接非互质节点形成的图中最大组件大小的教程的结尾。为了解决这个任务，需要初始化一个数组并找到一对节点。迭代节点以找到非互质的对。使用埃拉托斯特尼筛法算法来确定给定范围内的质因数。用一些示例演示了问题陈述以更好地理解逻辑。