# Count Connected Components in LCM Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-connected-components-in-lcm-graph)
Canonical: https://scaleengineer.com/dsa/problems/count-connected-components-in-lcm-graph
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array of integers `nums` of size `n` and a **positive** integer `threshold`.

There is a graph consisting of `n` nodes with the `ith` node having a value of `nums[i]`. Two nodes `i` and `j` in the graph are connected via an **undirected** edge if `lcm(nums[i], nums[j]) <= threshold`.

Return the number of **connected components** in this graph.

A **connected component** is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

The term `lcm(a, b)` denotes the **least common multiple** of `a` and `b`.

**Example 1:**

**Input:** nums = \[2,4,8,3,9\], threshold = 5

**Output:** 4

**Explanation:** 

![](https://assets.glich.co/dsa/count-connected-components-in-lcm-graph/image0.png)

The four connected components are `(2, 4)`, `(3)`, `(8)`, `(9)`.

**Example 2:**

**Input:** nums = \[2,4,8,3,9,12\], threshold = 10

**Output:** 2

**Explanation:** 

![](https://assets.glich.co/dsa/count-connected-components-in-lcm-graph/image1.png)

The two connected components are `(2, 3, 4, 8, 9)`, and `(12)`.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* All elements of `nums` are unique.
* `1 <= threshold <= 2 * 105`

# Approaches
## Brute-Force with Union-Find
The most straightforward approach is to model the problem directly. We can construct the graph by considering every possible pair of nodes and checking if an edge exists between them based on the LCM condition. After building the graph (or determining all edges), we can count the connected components.
**Time:** O(n^2 * log(max(nums))) due to iterating through O(n^2) pairs and performing a GCD calculation for each, which takes logarithmic time. · **Space:** O(n) for the DSU data structure.
**Pros:** Simple to understand and implement.; Correctly models the problem definition without complex transformations.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5), leading to a Time Limit Exceeded (TLE) error.; The space complexity for an explicit graph representation (adjacency list) could be up to O(n^2) in a dense graph, which is too large for the given memory limits.
### Explanation
This method involves iterating through all unique pairs of numbers in the input array `nums`. For each pair `(nums[i], nums[j])`, we check if they should be connected. The condition for an edge is `lcm(nums[i], nums[j]) <= threshold`. 

To manage the connected components, a Disjoint Set Union (DSU) or Union-Find data structure is ideal. We initialize `n` disjoint sets, one for each element in `nums`. Then, for each pair `(i, j)` that satisfies the LCM condition, we merge the sets to which `i` and `j` belong. 

The final count of disjoint sets gives the number of connected components in the graph.

```java
import java.math.BigInteger;

class Solution {
    public int countConnectedComponents(int[] nums, int threshold) {
        int n = nums.length;
        DSU dsu = new DSU(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long num_i = nums[i];
                long num_j = nums[j];
                
                long commonDivisor = gcd(num_i, num_j);
                // lcm(a,b) = (a / gcd(a,b)) * b to prevent overflow
                BigInteger lcm = BigInteger.valueOf(num_i / commonDivisor).multiply(BigInteger.valueOf(num_j));

                if (lcm.compareTo(BigInteger.valueOf(threshold)) <= 0) {
                    dsu.union(i, j);
                }
            }
        }

        return dsu.countSets();
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    class DSU {
        int[] parent;
        int count;

        public DSU(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                count--;
            }
        }

        public int countSets() {
            return count;
        }
    }
}
```
### Algorithm
1. Initialize a Disjoint Set Union (DSU) data structure with `n` sets, one for each number in `nums`.
2. Iterate through every pair of indices `(i, j)` where `0 <= i < j < n`.
3. For each pair, calculate the greatest common divisor (GCD) of `nums[i]` and `nums[j]` using the Euclidean algorithm.
4. Calculate the least common multiple (LCM) using the formula `lcm(a, b) = (a * b) / gcd(a, b)`. To avoid potential overflow with `a * b`, it's better to compute it as `(a / gcd(a, b)) * b`.
5. If `lcm(nums[i], nums[j]) <= threshold`, perform a union operation on the sets containing nodes `i` and `j`.
6. After checking all pairs, the number of connected components is the number of disjoint sets remaining in the DSU.

## Optimized Union-Find by Common Divisors
A more efficient approach avoids checking all `O(n^2)` pairs. The key observation is that the `threshold` is relatively small. We can filter out numbers greater than the `threshold` as they form singleton components. For the remaining numbers, we can use common divisors as a way to group numbers and check for connections more efficiently. Instead of checking all pairs, we iterate through possible common divisors `g` and only check for LCM conditions among numbers that share `g` as a divisor.
**Time:** O(n + T*log(T)*log(T)) where T is the threshold. The dominant part is iterating through divisors `g` from 1 to T. For each `g`, we iterate through its T/g multiples. The total number of pairs considered is much less than n^2. A loose upper bound is `O(T*log(T)*log(T))`. A tighter analysis shows the complexity is closer to `O(n + sum_{x in U} d(x)*log(T))`, where `d(x)` is the number of divisors of `x`, which is efficient enough. · **Space:** O(n + threshold) to store the filtered numbers, the value-to-index map, and the DSU structure.
**Pros:** Significantly more efficient than the brute-force approach.; Handles the given constraints within the time limit.; The initial filtering step is a simple and effective optimization.
**Cons:** The logic is more complex than the brute-force approach.; The time complexity depends on the number of divisors of numbers up to the threshold, which can be non-trivial to analyze precisely.
### Explanation
This approach optimizes the process of finding edges. We start by realizing that any number `num > threshold` can't be part of any edge, as `lcm(num, other) >= num > threshold`. These numbers form components of size one. We count them and focus on the remaining numbers, all of which are `<= threshold`.

We use a Union-Find data structure on these filtered numbers. The core idea is to iterate through each integer `g` from `1` to `threshold`. For each `g`, we identify all numbers in our filtered set that are multiples of `g`. Let's say we find a list of such multiples `M_g = [m_1, m_2, ..., m_k]`. Any pair from this list shares `g` as a common divisor. To form connections, we can pick the first multiple `m_1` and iterate through the rest `m_i`. If `lcm(m_1, m_i) <= threshold`, we union their sets. This transitively connects all numbers in `M_g` that should be in the same component.

This avoids checking pairs with small GCDs that would likely result in large LCMs. The total number of LCM checks is significantly reduced from `O(n^2)`.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int countConnectedComponents(int[] nums, int threshold) {
        List<Integer> filteredNums = new ArrayList<>();
        int initialComponents = 0;
        for (int num : nums) {
            if (num > threshold) {
                initialComponents++;
            } else {
                filteredNums.add(num);
            }
        }

        if (filteredNums.isEmpty()) {
            return initialComponents;
        }

        int m = filteredNums.size();
        DSU dsu = new DSU(m);
        Map<Integer, Integer> valToIdx = new HashMap<>();
        for (int i = 0; i < m; i++) {
            valToIdx.put(filteredNums.get(i), i);
        }

        for (int g = 1; g <= threshold; g++) {
            List<Integer> multiples = new ArrayList<>();
            for (int multiple = g; multiple <= threshold; multiple += g) {
                if (valToIdx.containsKey(multiple)) {
                    multiples.add(multiple);
                }
            }

            if (multiples.size() > 1) {
                int firstVal = multiples.get(0);
                int firstIdx = valToIdx.get(firstVal);
                for (int i = 1; i < multiples.size(); i++) {
                    int currentVal = multiples.get(i);
                    int currentIdx = valToIdx.get(currentVal);
                    // lcm(a,b) = (a/gcd(a,b))*b. Here gcd(firstVal, currentVal) >= g.
                    // No need to check lcm, as if a,b are multiples of g and a+b <= threshold, then lcm(a,b) <= threshold.
                    // But a simpler, correct approach is to just check the lcm condition.
                    long commonDivisor = gcd(firstVal, currentVal);
                    if ((long)firstVal * currentVal / commonDivisor <= threshold) {
                         dsu.union(firstIdx, currentIdx);
                    }
                }
            }
        }

        return initialComponents + dsu.countSets();
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    class DSU {
        int[] parent;
        int count;

        public DSU(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                count--;
            }
        }

        public int countSets() {
            return count;
        }
    }
}
```
### Algorithm
1. First, handle numbers larger than the `threshold`. Any `nums[i] > threshold` cannot have an LCM with any other number `nums[j]` that is less than or equal to the `threshold`, because `lcm(a, b) >= max(a, b)`. Thus, each such number forms its own connected component of size one.
2. Create a new list, `filtered_nums`, containing only the numbers from `nums` that are less than or equal to the `threshold`.
3. If `filtered_nums` is empty, the answer is just the count from step 1.
4. Create a map `val_to_idx` to quickly find the index of a number in `filtered_nums`.
5. Initialize a DSU data structure for the elements in `filtered_nums`.
6. Iterate through all possible common divisors `g` from `1` to `threshold`.
7. For each `g`, find all multiples of `g` that are present in `filtered_nums`. Let this list be `M_g`.
8. If `M_g` contains more than one number, pick the first one, `p`. Then, for every other number `q` in `M_g`, check if `lcm(p, q) <= threshold`. If it is, union the sets for `p` and `q`.
9. The total number of components is the count from step 1 plus the final number of disjoint sets in the DSU.

# Solutions
### Java

```java
class DSU { private Map < Integer , Integer > parent ; private Map < Integer , Integer > rank ; public DSU ( int n ) { parent = new HashMap <>(); rank = new HashMap <>(); for ( int i = 0 ; i <= n ; i ++) { parent . put ( i , i ); rank . put ( i , 0 ); } } public void makeSet ( int v ) { parent . put ( v , v ); rank . put ( v , 1 ); } public int find ( int x ) { if ( parent . get ( x ) != x ) { parent . put ( x , find ( parent . get ( x ))); } return parent . get ( x ); } public void unionSet ( int u , int v ) { u = find ( u ); v = find ( v ); if ( u != v ) { if ( rank . get ( u ) < rank . get ( v )) { int temp = u ; u = v ; v = temp ; } parent . put ( v , u ); if ( rank . get ( u ). equals ( rank . get ( v ))) { rank . put ( u , rank . get ( u ) + 1 ); } } } } class Solution { public int countComponents ( int [] nums , int threshold ) { DSU dsu = new DSU ( threshold ); for ( int num : nums ) { for ( int j = num ; j <= threshold ; j += num ) { dsu . unionSet ( num , j ); } } Set < Integer > uniqueParents = new HashSet <>(); for ( int num : nums ) { if ( num > threshold ) { uniqueParents . add ( num ); } else { uniqueParents . add ( dsu . find ( num )); } } return uniqueParents . size (); } }
```

### CPP

```cpp
typedef struct DSU { unordered_map < int , int > par , rank ; DSU ( int n ) { for ( int i = 0 ; i < n ; ++ i ) { par [ i ] = i ; rank [ i ] = 0 ; } } void makeSet ( int v ) { par [ v ] = v ; rank [ v ] = 1 ; } int find ( int x ) { if ( par [ x ] == x ) { return x ; } return par [ x ] = find ( par [ x ]); } void unionSet ( int u , int v ) { u = find ( u ); v = find ( v ); if ( u != v ) { if ( rank [ u ] < rank [ v ]) swap ( u , v ); par [ v ] = u ; if ( rank [ u ] == rank [ v ]) rank [ u ] ++ ; } } } DSU ; class Solution { public: int countComponents ( vector < int >& nums , int threshold ) { DSU dsu ( threshold ); for ( auto & num : nums ) { for ( int j = num ; j <= threshold ; j += num ) { dsu . unionSet ( num , j ); } } unordered_set < int > par ; for ( auto & num : nums ) { if ( num > threshold ) { par . insert ( num ); } else { par . insert ( dsu . find ( num )); } } return par . size (); } };
```

### Python

```python
class DSU : def __init__ ( self , n ): self . parent = { i : i for i in range ( n )} self . rank = { i : 0 for i in range ( n )} def make_set ( self , v ): self . parent [ v ] = v self . rank [ v ] = 1 def find ( self , x ): if self . parent [ x ] != x : self . parent [ x ] = self . find ( self . parent [ x ]) return self . parent [ x ] def union_set ( self , u , v ): u = self . find ( u ) v = self . find ( v ) if u != v : if self . rank [ u ] < self . rank [ v ]: u , v = v , u self . parent [ v ] = u if self . rank [ u ] == self . rank [ v ]: self . rank [ u ] += 1 class Solution : def countComponents ( self , nums , threshold ): dsu = DSU ( threshold + 1 ) for num in nums : for j in range ( num , threshold + 1 , num ): dsu . union_set ( num , j ) unique_parents = set () for num in nums : if num > threshold : unique_parents . add ( num ) else : unique_parents . add ( dsu . find ( num )) return len ( unique_parents )
```