Last Updated: 3 Jan, 2021
Largest Component
Moderate
Asked in companies
You are given an array 'ARR' of size 'N' containing positive integers. Consider an undirected graph using the given array with the following conditions:
-> The graph consists of 'N' vertices.
-> The ith vertex has a value 'ARR[i]'.
-> There is an edge between two vertices 'i' and 'j' (where 'i' < 'j'), if and only if GCD('ARR[i]', 'ARR[j]') is greater than 1.
GCD(a, b) is the maximum number x such that both a and b are divisible by x.
Your task is to find the size of the largest component in the graph.
A component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph. The size of a component is the number of vertices in it.
Input format :
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases are as follows.
The first line of each test case contains a positive integer 'N', which represents the size of the array 'ARR'.
The next line contains 'N' single space-separated positive integers representing the elements of the array.
Output Format :
For each test case, print an integer denoting the size of the largest component in the graph.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^3
1 <= ARR[i] <= 10^5
Where 'ARR[i]' is the ith element in the array.
Time Limit: 1 sec
Approaches
In this approach, we will make the graph, for this, we will make an adjacency list to store the edges of the graph. Iterate on the vertices using two loops and add an edge between vertex i and j, if GCD('ARR[i]', ‘ARR[j]’) is greater than 1.
Now, find the size of every component in the graph. We can do this using DFS.
- Make an array to store the visited vertices.
- Iterate on the vertex of the graph
- If a vertex ‘v’ is unvisited, run a DFS from the vertex 'v'.
- In the DFS, we will visit all the vertices which are reachable from the vertex ‘v’.
- This will form one component with its size being the number of vertices we visit in the DFS.
- Else, continue.
Two numbers have GCD greater than 1 if they have a common prime factor.
We will use DSU to find the size of components, and each set represents one component.
Initially, there will be ‘N’ sets, each containing one vertex. We will combine two sets if they have some common prime factor.
For example:
If we have given vertex values as {10, 4, 2, 5, 3, 9}.
Note: P.F., denotes Prime Factors.
Set 1 contains {10}, P.F. are {2, 5}.
Set 2 contains {4}, P.F. are {2}.
Set 3 contains {2}, P.F. are {2}.
Set 4 contains {5}, P.F. are {5}.
Set 5 contains {3}, P.F. are {3}.
Set 6 contains {9}, P.F. are {3}.
We can combine set 2 in set 1, because 2 is the common prime factor present in both sets.
Now set 1 contains {10, 4}, P.F. are {2, 5}.
We can combine set 3 in set 1, because 2 is the common prime factor present in both sets.
Now set 1 contains {10, 4, 2}, P.F. are {2, 5}.
We can combine set 4 in set 1, because 5 is the common prime factor present in both sets.
Now set 1 contains {10, 4}, P.F. are {2, 5}.
We can combine set 6 in set 5, because 3 is the common prime factor present in both sets.
Now set 5 contains {3, 9}, P.F. are {3}.
In the end, we have two sets 1 and 5.
Set 1 contains {10, 4, 2, 5}.
Set 5 contains {3,9}.
These final two sets represent the two components of the graph.
Algorithm:
- First, find the prime factors of every vertex value.
- Initialise ‘N’ sets, each containing one vertex.
- For every prime factor, we find if there is a set containing this prime factor. For this, we will make an array ‘ISPRESENT’.
- If there is no set containing ‘X’ as a prime factor, then ‘ISPRESENT[X]’ is equal to -1.
- Else, ‘ISPRESENT[X]’ is equal to the set number which contains ‘X’ as a prime factor.
- Iterate on the vertices, let ‘v’ denote the current vertex.
- Iterate on the prime factors of ‘v’, let ‘X’ denote the current prime factor.
- If ‘ISPRESENT[X]’ is not equal to -1, then combine the set containing vertex ‘v’ and the set containing ‘X’ as a prime factor.
- Return the size of the set, which is maximum.