数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学由互质数节点连接而成的图中最大连通分量的大小
介绍
本教程讨论了使用C++查找由连接非互质数节点生成的图中最大连通分量大小的问题。图由通过边连接的节点组成。图的连通分量是构成节点的值的子集。有一个数组a[]构成图G。图的连通分量是构成节点的值的子集。非互质数是指最大公约数(HCF)不为1的数，这意味着它们有一些其他的公因子。在本教程中，我们将使用两种不同的方法来解决这个问题。
示例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_name.push_back(value);
auto: 它是C++中的关键字。它用于自动为变量分配数据类型。它是编译时变量的自动类型声明。
auto variable_name;
set: 它是C++中收集唯一元素的容器。集合中的所有元素都是排序的。
set<data_type> set_name;
max(): 它在C++库的`
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++查找由连接非互质数节点而成的图中最大连通分量的大小。为了解决此任务，我们初始化一个数组并查找节点对。遍历节点以查找非互质对。使用埃拉托色尼筛法识别给定范围内的质因子。通过一些示例演示了问题陈述，以便更好地理解逻辑。
83 次浏览
