資料結構
網路
關係資料庫管理系統 (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 次瀏覽
