题目描述：
LeetCode 952. Largest Component Size by Common Factor
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，构造一个图：
包含A.length个顶点，标号为A[0]到A[A.length - 1]；
当且仅当A[i]和A[j]有大于1的公因子时，A[i]与A[j]之间有边相连。
返回图中的最大连同分量的大小。
解题思路：
并查集（Union Find Set）
构造从数字a到其所有质因子的映射facnum
构造从质因子到原始数字a的反向映射numfac
令映射caps = facnum，表示以k为顶点的连同分量的顶点集合
将A中的每个数a进行质因子分解，得到所有数的质因子集合factors
遍历factors，记质因数为f
遍历f的所有原始数字，记为n
遍历n的所有质因子，记为g
merge(f, g)，在merge操作中对caps进行合并
Python代码：
class Solution(object):
def largestComponentSize(self, A):
"""
:type A: List[int]
:rtype: int
"""
facnum = collections.defaultdict(set)
numfac = collections.defaultdict(set)
caps = collections.defaultdict(set)
for a in A:
facs = self.primeFactors(a)
for f in facs:
facnum[f].add(a)
caps[f].add(a)
numfac[a].add(f)
factors = facnum.keys()
parents = {f : f for f in factors}
def find(x):
while parents[x] != x:
x = parents[x]
return x
def merge(x, y):
x = find(x)
y = find(y)
parents[y] = x
caps[x] |= caps[y]
for f in factors:
for n in facnum[f]:
for g in numfac[n]:
if f != g: merge(f, g)
ans = 0
for f in factors:
ans = max(ans, len(caps[find(f)]))
return ans
def primeFactors(self, n):
factors = set()
i = 2
while i * i <= n:
if n % i:
i += 1
else:
n /= i
factors.add(i)
if n > 1:
factors.add(n)
return factors
本文链接：http://bookshadow.com/weblog/2018/12/02/leetcode-largest-component-size-by-common-factor/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
