Description
Given a non-empty array of unique positive integers A, consider the following graph:
- There are
A.lengthnodes, labelledA[0]toA[A.length - 1]; - There is an edge between
A[i]andA[j]if and only ifA[i]andA[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 
Note:
1 <= A.length <= 200001 <= A[i] <= 100000
这道题给了一个非空正数数组A，现在将每个数字看作一个结点，定义两个结点相连的条件是两个数字共享一个大于1的因子，求最大的相连的结点个数。这道题看似像一个图的问题，其实跟图并没有太大的关系，本质上就是群组问题，这种归组类的问题，最典型的就是岛屿问题(例如 Number of Islands II)，很适合使用联合查找 Union Find 来做，也叫并查集，LeetCode 中有很多道可以使用这个方法来做的题，比如 Friend Circles，Graph Valid Tree，Number of Connected Components in an Undirected Graph，和 Redundant Connection 等等。都是要用一个 root 数组，每个点开始初始化为不同的值，如果两个点属于相同的组，就将其中一个点的 root 值赋值为另一个点的位置，这样只要是相同组里的两点，通过 find 函数得到相同的值。这里也是一样，我们希望把所有至少共享一个大于2的因子的数字都放到一个群组中，那么初始化数组的大小就应该是数组A中最大的数字加1，因为数组序列是0开头的。先遍历一遍数组A，找出最大数字，然后建立 root 数组初始化为不同的群组。之后遍历数组A，对于每个数字，找出其所有大于2的因子，由于因子都是成对出现的，所以只需要从其平方根遍历到2即可，每当找到一对因子，分别将其跟原数组合并起来，注意在更新 root 数组的时候，对于每个数字都要调用 find 函数，这里希望将同一个群组的 root 值都更新为相同的值，这样方便后面统计每个群组中结点的个数。当所有的因子都合并完成了之后，下面进行查找操作，使用一个 HashMap 来建立群组祖先结点值和结点个数之间的映射。对于每个遍历到的数组，通过 find 函数查找祖先值，然后将其在 HashMap 中映射值自增1，然后用更新后的值来更新结果 res 即可，参见代码如下：
class Solution { public: int largestComponentSize(vector<int>& A) { int n = 0, mx = 0, res = 0; unordered_map<int, int> m; for (int num : A) mx = max(mx, num); vector<int> root(mx + 1); for (int i = 1; i <= mx; ++i) root[i] = i; for (int num : A) { for (int d = sqrt(num); d >= 2; --d) { if (num % d == 0) { root[find(root, num)] = root[find(root, d)]; root[find(root, num)] = root[find(root, num / d)]; } } } for (int num : A) { res = max(res, ++m[find(root, num)]); } return res; } int find(vector<int>& root, int x) { return root[x] == x ? x : (root[x] = find(root, root[x])); } }; Github 同步地址:
参考资料：
https://leetcode.com/problems/largest-component-size-by-common-factor/