# 952     Largest Component Size by Common Factor

## 952. [Largest Component Size by Common Factor](https://leetcode.com/problems/largest-component-size-by-common-factor/)

## 1. Question

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 1:**

```
Input: [4,6,15,35]
Output: 4
```

**Example 2:**

```
Input: [20,50,9,63]
Output: 2
```

**Example 3:**

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

## 2. Implementation

**(1) Union Find**

思路: 对于每个数，我们找出所有它的factor，将它自己与factor通过union-find联合起来， 最后遍历一遍输入数组，通过union-find找到其所属的component，看看哪个component包含输入数组的数字最多即可

```java
class Solution {
    public int largestComponentSize(int[] A) {
        int maxNum = 0;

        for (int num : A) {
            maxNum = Math.max(maxNum, num);
        }

        UnionFind uf = new UnionFind(maxNum + 1);

        for (int num : A) {
            int upperBound = (int)Math.sqrt(num);

            for (int factor = 2; factor <= upperBound; factor++) {
                if (num % factor == 0) {
                    uf.union(num, factor);
                    uf.union(num, num / factor);
                }
            }
        }

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

        for (int num : A) {
            int root = uf.find(num);
            map.put(root, map.getOrDefault(root, 0) + 1);
            res = Math.max(res, map.get(root));
        }
        return res;
    }

    class UnionFind {
        int[] root;
        int[] size;
        int maxSize;

        public UnionFind(int n) {
            root = new int[n];
            size = new int[n];

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

        public int find(int node) {
            while (node != root[node]) {
                node = root[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int p = find(i);
            int q = find(j);

            if (p == q) return;

            if (size[p] < size[q]) {
                root[p] = q;
                size[q] += size[p];
            }
            else {
                root[q] = p;
                size[p] += size[q];
            }
        }
    }
}
```

## 3. Time & Space Complexity

Union Find: 时间复杂度O(n \* Sqrt(W)), n是输入数组的size，W是输入数组的最大数。空间复杂度O(W)
