## 题目描述：

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.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

```

Note:

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

## 解题思路：

```构造从数字a到其所有质因子的映射facnum

遍历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:

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
if n > 1:
return factors
``````

Pingbacks已关闭。