Largest Component Size by Common Factor

The idea is to use a disjoint set data structure. We will maintain a disjoint set where different numbers are linked together if and only if they have a common factor greater than 1. So, we have to link each element in ‘VERTICES’ with all its factors greater than 1. For this purpose, we will check all the integers ranging from 2 to sqrt(VERTICES[i]). Since if ‘X’ is a factor of ‘P’ then ‘P / X’ is also a factor of 'P’.

After linking, we only have to find which set has the maximum number of elements from the ‘VERTICES’ array. This can be done by maintaining the frequency of the representative element of every set. We will count the elements from ‘VERTICES’ that have the given representative element and output the maximum such frequency.
 

Algorithm:

• Declare an integer variable, ‘result’ initialize with zero. The ‘result’ will hold the size of the largest connected component.
• Find the maximum element present in ‘vertices’ and store it in an integer variable, ‘maxElement’.
• Create an object ‘ds’ of ‘DisjointSet’ and pass ‘maxElement + 1’ as the parameter.
• Run a loop for every element, ‘num’ in the ‘vertices’.
  • Run a loop from i = 2 to sqrt(num).
    • If num % i == 0 that shows that ‘i’ is a factor of ‘num’. Therefore,
      • Add ‘i’ and ‘num’ in the same set by calling ‘ds.Union’ function.
      • Add ‘num / i’ and ‘num’ in the same set by calling ‘ds.Union’ function.
• Declare a hashmap, ‘hashMap’ to store the frequency of representative elements.
• Run a loop for every element, ‘num’ in the ‘vertices’.
  • Find the representative element of ‘num’ by ‘ds.find’ function and store it in an integer variable, ‘numRep’.
  • Increment ‘hashMap[numRep]’ by 1.
  • Update ‘result’ by ‘max(result, hashMap[numRep])’.
• In the end, return ‘result’.

Description of ‘DisjointSet’ class

private:

The private part of the ‘DisjointSet’ class will contain two data members:

• parent: An integer array to store the parent of each vertex in the graph.
• rank: An integer array to store the rank of each vertex in the graph.

public:

The private part of the ‘DisjointSet’ class will contain one constructor and two member functions:

Description of ‘DisjointSet’ constructor

The constructor will take one parameter:

• n: An integer variable that represents the number of vertices in the graph (i.e., number of points in the ‘coordinates’ array).

DisjointSet(n):

• Resize the size of the ‘parent’ and ‘rank’ array to ‘n’.
• Run a loop from i = 0 to n - 1.
  • Assign ‘i’ to ‘parent[i]’ and set ‘rank[i]’ to zero.

Description of ‘find’ function

The function will take one parameter:

• x: An integer variable that represents the vertex (element) whose representative element has to be searched.

find(x):

• If parent[x] == x that shows that ‘X’ itself is the representative element. So, return ‘X’.
• Else, call the ‘find’ function for ‘parent[x]’ and store the returned result in ‘parent[x]’.
• Return ‘parent[x]’.

Description of ‘Union’ function

The function will take two parameters:

• u: An integer variable that represents vertex in the graph (or point in ‘coordinates’ array).
• v : Another integer variable that represents vertex in the graph (or point in ‘coordinates’ array).

Union(u, v):

• Pass ‘u’ to the ‘find’ function and store the returned value in an integer variable, ‘uRep’.
• Pass ‘v’ to the ‘find’ function and store the returned value in an integer variable, ‘vRep’.
• If uRep == vRep that shows ‘u’ and ‘v’ are already in the same set. So, return.
• Else if rank[uRep] < rank[vRep] that shows that the rank of ‘uRep’ is less than the rank of ‘vRep’.
  • Update parent of ‘uRep’ by ‘vRep’.
• Else if rank[uRep] > rank[vRep] that shows that the rank of ‘uRep’ is more than the rank of ‘vRep’.
  • Update parent of ‘vRep’ by ‘uRep’.
• Else rank of ‘uRep’ and ‘vRep’ are the same.
  • Update parent of ‘uRep’ by ‘vRep’.
  • Increment rank of ‘vRep’ by 1.

O(N * sqrt(maxElement)), where ‘N’ is the size of ‘vertices’ array and ‘maxElement’ is the maximum element in the ‘vertices’ array.

The time complexity of linking factors of every element to a parent element is O(N * sqrt(maxElement)). Since the loop will make ‘N’ iterations and in every iteration, we are traversing till sqrt(num) which will be sqrt(maxElement) in the worst case.

The time complexity of finding the maximum frequency of representative element is O(N * log(maxElement)). Since the for loop will make ‘N’ iterations and in every iteration, we are finding the representative element of ‘num’ which is O(log(num)) operation that will become log(maxElement) in the worst case.

Hence, overall time complexity is O(N * sqrt(maxElement)) + O(N * log(maxElement)) = O(N * sqrt(maxElement)).

O(maxElement), where ‘maxElement’ is the maximum element in the ‘vertices’ array.

Since O(maxElement) space is required for the DisjointSet ‘ds’ object and also for ‘hashMap’ in the worst case.