Largest Component Size In A Graph Formed By Connecting Non Co Prime Nodes In C++

In this tutorial, we are going to explore the challenge of determining the largest component size in a Graph created by linking non-coprime nodes using C++. The connectivity between nodes in the graph is established through edges. The constituents of the graph consist of a collection of values that serve as nodes. A graph, denoted as G, is constructed based on a series of values from array a. These values are extracted from the component set that constructs the nodes of the graph. Non-coprime numbers are those numbers that share a Greatest Common Factor (GCF) greater than 1, making them not mutually prime. In this context, two distinct methodologies are employed.

Now when dealing with a graph comprising N nodes, we assign values A to each of these nodes. To calculate the size of the largest connected section in the graph, we evaluate the connections between nodes that do not have a coprime relationship. In the case where nodes U and V are not coprime, there exists a connection between them. This indicates that if the highest common factor of A[U] and A[V] is more than 1.

Example:

Input: {12,4,5,45,12,5,11,49}

Output: 6

Approach 1: Naive Approach

We will initiate by considering the collection of all node pairs and then confirming their co-primality status. In cases where the nodes are not both coprime integers, we will determine the appropriate course of action. Subsequently, we will follow the Depth First Search algorithm to determine the magnitude of the most extensive connected component.

The below code describes the implementation:

Example:

#include <bits/stdc++.h>
using namespace std;
int dfs_search(int u, vector<int>* adjacent, int visited[])
{
	// marking up the visited node
	visited[u] = 1;
	int eleLength = 1;

	// the dfs search to add nodes
	for (auto ite : adjacent[u]) {
		if (!visited[ite]) {
			eleLength += dfs_search(ite, adjacent, visited);
		}
	}
	return eleLength;
}
int maximumComponentLength(int a[], int num)
{
	// the graph creation
	vector<int> adjacent[num];

	// the for loop to iterate over all nodes of the graph
	for (int i = 0; i < num; i++) {
		for (int j = i + 1; j < num; j++) {
			//If not co-prime
			if (__gcd(a[i], a[j]) > 1)
				// the undirected graph
				adjacent[i].push_back(j);
			adjacent[j].push_back(i);
		}
	}
	int result = 0;

	// the visited array for storing DFS values
	int visited[num];
	for(int k=0;k<num;k++){
	visited[k]=0;
	}
	for (int i = 0; i < num; i++) {
		if (!visited[i]) {
			result = max(result, dfs_search(i, adjacent, visited));
		}
	}
	return result;
}

// Main Code
int main()
{
	int num = 8;
	int A[] = { 23,12,7,4,2,9,21,78};
	cout << maximumComponentLength(A, num);
	return 0;
}

Output:

Explanation:

• ✅ The code writes a function named dfs_search that performs depth-first search on a graph.
• ✅ In this example, the dfs_search function initially behaves on the start node, marking it as visited and recursively searching through the unvisited neighbors.
• ✅ The function maxComponentLength implements a graph based on an array of numbers, where numbers that are not co-prime are added as edges. The function starts with an array called visited to track visited nodes and uses DFS to find the length of the largest connected component.
• ✅ The main function creates an array, assigns data to it, and calls maximumComponentLength to discover the length of the longest connected component and print it.

Approach 2: Efficient Approach

If two numbers share a common divisor, they are considered non-coprime. As a result, the most efficient path will be determined based on the prime factorization of the values assigned to the nodes.

Completing prime factorization accurately involves utilizing the sieve of Eratosthenes method. Grouping adjacent nodes is achieved by implementing the disjoint set data structure, which incorporates rank increase and path compression techniques.

The organization of the data operates in this manner. When

• ✅ p[i] <- stands for the parent of node i.
• ✅ size[i] denotes the level of i.
• ✅ id(p) -> is encountered, it signifies that the value of p was the initial one to be identified as a divisor of the element A[i].

We will break down the value of each node into prime numbers and save them in set S. Proceed through each prime number in set S. If a prime number is encountered as a factor for the first time (id[p] is zero), assign the current index to that prime. If id[p] has already been assigned, combine the current node with the one at id[p]. The following illustration demonstrates an effective method:

Example:

#include <bits/stdc++.h>
using namespace std;
//an array of small prime number
int small_factor[100005];
// the sieve method
void sieve_Method()
{
	for (int i = 2; i < 100005; i++) {
		//If the condition is true, then it is a prime number
		if (small_factor[i] == 0) {
			small_factor[i] = i;

			for (int j = 2 * i; j < 100005; j += i) {

				// the smallest prime factor which has prime numbers
				if (small_factor[j] == 0)
					small_factor[j] = i;
			}
		}
	}
}

// The prime factors are stored in the set
void fact_number(int num, set<int>& set)
{

	while (num > 1) {
		int z1 = small_factor[num];
		set.insert(z1);
		while (num % z1 == 0)
			num /= z1;
	}
}

int id[100005];
int parm[100005];
int sizeVal[100005];

// the root node of the component
int rootNode(int i)
{
	if (parm[i] == i)
		return i;
	// 
	else
		return parm[i] = rootNode(parm[i]);
}

// the function for merging of two nodes
void mergeNodes(int a1, int b1)
{

	//Finding the root for both of the components
	int p1 = rootNode(a1);
	int q1 = rootNode(b1);

	
	if (p1 == q1)
		return;

	//The find root value is calculated
	if (sizeVal[p1] > sizeVal[q1])
		swap(p1, q1);

	parm[p1] = q1;
	sizeVal[q1] += sizeVal[p1];
}

// function for finding the maximum value
int maxComponent(int a1[], int num)
{
	// initialization of the component
	for (int i = 0; i < 100005; i++) {
		// initial value is set to 1
		parm[i] = i;
		sizeVal[i] = 1;
	}

	sieve_Method();

	for (int i = 0; i < num; i++) {
		//The prime factors are stored in the set sset
		set<int> sset;
		fact_number(a1[i], sset);

		for (auto it : sset) {
			//If this prime is seen as a factor
			// for the first time
			if (id[it] == 0)
				id[it] = i + 1;
			//If it was not found, merge it to the previous
			else
				mergeNodes(i + 1, id[it]);
		}
	}

	int result = 0;

	//the maximum value
	for (int i = 0; i < num; i++)
		result = max(result, sizeVal[i]);

	return result;
}

// Driver Code
int main()
{
	int num = 8;
	int Array[] = { 12, 13, 6, 27, 4, 8, 21, 9 };

	cout << maxComponent(Array, num);

	return 0;
}

Output:

Explanation:

• ✅ In this example, the code sets an array small_factor, which contains the smallest prime factors for those numbers not larger than 100,004. It will be applied to prime factorization.
• ✅ The sieveMethod function uses the sieve of the Eratosthenes algorithm to fill the smallfactor array with values. It factors out the smallest prime number for each of the numbers.
• ✅ The fact_number function finds the prime factors of the number num and puts them in the set.
• ✅ The code defines arrays as id, parm, and sizeVal to store component information. Ip refers to the initial position of the prime factor in the list. The parm variable keeps the component's parent node, and sizeVal saves the component's size.
• ✅ The rootNode function is responsible for finding a component's root based on the union-find algorithm. It uses path compression to speed up subsequent searches.
• ✅ The mergeNodes method merges two components by changing their root nodes and sizes.
• ✅ The maxComponent function takes the inputs and calculates the main component. It initializes objects, calls the method sieve, and goes over the input array.
• ✅ It calculates the prime factors for every element in an input array and keeps a set of them in a set named sset. It also decides whether the prime factor has been seen before.
• ✅ Whenever a prime factor for the first time (id[it] == 0), sets a value of the current index plus one to id[it]. Instead, it combines the current element with the id[it] element.
• ✅ After going through all the numbers, the function finds the maximum component size by looping over them and storing the value in a variable.
• ✅ In the end, the main function inputs an array of numbers in the space and now calls maxComponent , which will find the maximum component size and show it.