Skip to content

3378. Count Connected Components in LCM Graph

Description

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: 

 

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: 

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

Solutions

Solution 1: Union Find

Thinking

Two values are joined when their LCM is at most \(\textit{threshold}\). With \(n \le 10^5\) and \(\textit{threshold} \le 2 \times 10^5\) we cannot try every pair.

Numbers that share a multiple inside the threshold become connected through that multiple. Union each \(\textit{num}\) with every multiple up to the threshold.

Values larger than the threshold have no edge and form singleton components. The remaining answer is the number of distinct DSU roots.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
type DSU struct {
    parent map[int]int
    rank   map[int]int
}

func NewDSU(n int) *DSU {
    dsu := &DSU{
        parent: make(map[int]int),
        rank:   make(map[int]int),
    }
    for i := 0; i <= n; i++ {
        dsu.parent[i] = i
        dsu.rank[i] = 0
    }
    return dsu
}

func (dsu *DSU) Find(x int) int {
    if dsu.parent[x] != x {
        dsu.parent[x] = dsu.Find(dsu.parent[x])
    }
    return dsu.parent[x]
}

func (dsu *DSU) Union(u, v int) {
    uRoot := dsu.Find(u)
    vRoot := dsu.Find(v)
    if uRoot != vRoot {
        if dsu.rank[uRoot] < dsu.rank[vRoot] {
            uRoot, vRoot = vRoot, uRoot
        }
        dsu.parent[vRoot] = uRoot
        if dsu.rank[uRoot] == dsu.rank[vRoot] {
            dsu.rank[uRoot]++
        }
    }
}

func countComponents(nums []int, threshold int) int {
    dsu := NewDSU(threshold)

    for _, num := range nums {
        for j := num; j <= threshold; j += num {
            dsu.Union(num, j)
        }
    }

    uniqueParents := make(map[int]struct{})
    for _, num := range nums {
        if num > threshold {
            uniqueParents[num] = struct{}{}
        } else {
            uniqueParents[dsu.Find(num)] = struct{}{}
        }
    }

    return len(uniqueParents)
}

Solution 2: DFS

Thinking

Union-find needs ranks and compression. If we only count components, an explicit graph plus DFS is enough.

Each \(\textit{num}\) is joined to \(2\textit{num},3\textit{num},\ldots\); values above the threshold add one component and are skipped.

DFS from every unvisited \(\textit{num}\) inside the threshold counts one component per tree. Connectivity matches method one with a simpler implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def dfs(self, node, adj, vis):
        if vis[node]:
            return
        vis[node] = True
        for neighbor in adj[node]:
            self.dfs(neighbor, adj, vis)

    def countComponents(self, nums, threshold):
        adj = [[] for _ in range(threshold + 1)]
        vis = [False] * (threshold + 1)
        ans = 0

        for num in nums:
            if num > threshold:
                ans += 1
                continue
            for j in range(2 * num, threshold + 1, num):
                adj[num].append(j)
                adj[j].append(num)

        for num in nums:
            if num <= threshold and not vis[num]:
                self.dfs(num, adj, vis)
                ans += 1

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        if (visited[node]) return;
        visited[node] = true;
        for (int neighbor : adj.get(node)) {
            dfs(neighbor, adj, visited);
        }
    }

    public int countComponents(int[] nums, int threshold) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= threshold; i++) {
            adj.add(new ArrayList<>());
        }
        boolean[] visited = new boolean[threshold + 1];
        int ans = 0;

        for (int num : nums) {
            if (num > threshold) {
                ans++;
                continue;
            }
            for (int j = 2 * num; j <= threshold; j += num) {
                adj.get(num).add(j);
                adj.get(j).add(num);
            }
        }

        for (int num : nums) {
            if (num <= threshold && !visited[num]) {
                dfs(num, adj, visited);
                ans++;
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
private:
    void dfs(int node, vector<vector<int>> &adj, vector<bool> &vis) {
        if (vis[node]) return;
        vis[node] = true;
        for (auto &u : adj[node]) {
            dfs(u, adj, vis);
        }
    }

public:
    int countComponents(vector<int> &nums, int threshold) {
        vector<vector<int>> adj(threshold + 1);
        vector<bool> vis(threshold + 1, false);
        int ans = 0;
        for (auto &num : nums) {
            if (num > threshold) {
                ++ans;
                continue;
            }
            for (int j = 2 * num; j <= threshold; j += num) {
                adj[num].push_back(j);
                adj[j].push_back(num);
            }
        }
        for (auto &num : nums) {
            if (num <= threshold && !vis[num]) {
                dfs(num, adj, vis);
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func dfs(node int, adj [][]int, visited []bool) {
    if visited[node] {
        return
    }
    visited[node] = true
    for _, neighbor := range adj[node] {
        dfs(neighbor, adj, visited)
    }
}

func countComponents(nums []int, threshold int) int {
    adj := make([][]int, threshold+1)
    for i := range adj {
        adj[i] = []int{}
    }

    visited := make([]bool, threshold+1)
    components := 0

    for _, num := range nums {
        if num > threshold {
            components++
            continue
        }
        for j := 2 * num; j <= threshold; j += num {
            adj[num] = append(adj[num], j)
            adj[j] = append(adj[j], num)
        }
    }

    for _, num := range nums {
        if num <= threshold && !visited[num] {
            dfs(num, adj, visited)
            components++
        }
    }

    return components
}

Comments