[Leetcode] Problem 952 - Largest Component Size by Common Factor

Posted on | In ,

Given a non-empty array of unique positive integers A, consider the following graph:

  • There are A.length nodes, labelled A[0] to A[A.length - 1];
  • There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example

No.1

Input: [4,6,15,35]

Output: 4

0a5Pzj.png

No.2

Input: [20,50,9,63]

Output: 2

0a5eoT.png

No.3

Input: [2,3,6,7,4,12,21,39]

Output: 8

0a5wSH.png

Note

  1. 1 <= A.length <= 20000
  2. 1 <= A[i] <= 100000

Code

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
65
66
67
68
public class UnionFind {
    private int[] id;
    private int[] size;

    public UnionFind(int n) {
        this.id = new int[n + 1];
        this.size = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    public boolean union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return false;

        if (size[pRoot] < size[qRoot]) {
            id[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        } else {
            id[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }

        return true;
    }

    public int find(int p) {
        while (p != id[p])
            p = id[p];

        return p;
    }
}

public int largestComponentSize(int[] A) {
    int result = 0;
    Arrays.sort(A);
    int maxNum = A[A.length - 1];
    UnionFind uf = new UnionFind(maxNum);

    for (int a : A) {
        double sqrt = Math.sqrt(a);

        for (int i = 2; i <= sqrt; i++) {
            if (a % i == 0) {
                uf.union(a, i);
                uf.union(a, a / i);
            }
        }
    }

    Map<Integer, Integer> map = new HashMap<>();

    for (int a : A) {
        int root = uf.find(a);
        map.putIfAbsent(root, 0);
        map.put(root, map.get(root) + 1);
        result = Math.max(map.get(root), result);
    }

    return result;
}