企业官网建设流程全解析

LeetCode 2709 Greatest Common Divisor Traversal 全解：五种解法从暴力 DFS 到埃氏筛优化（并查集与图论实战）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南以 LeetCode 2709「Greatest Common Divisor Traversal」为核心，完整讲解将"两数最大公约数大于 1"这一数论关系转化为图连通性问题的建模思路，并给出从暴力 DFS、并查集（Union-Find/DSU）、试除质因数分解到"埃氏筛最小质因子 + DSU / DFS / BFS"共五种解法的逐步推导、完整多语言实现与复杂度分析。读完本文，你将掌握 DSU 的路径压缩与按秩合并写法、SPF（Smallest Prime Factor）筛的构建方法、虚拟质数节点在图/并查集中的偏移技巧，以及本仓库（LeetCode 多语言解决方案仓库）中该题的工程化实现细节。

前置知识

在动手实现之前，先确认你已具备以下五项基础能力。它们分别对应本文五种解法中的不同环节：

• 图遍历（DFS / BFS）：本题把数组下标建模为节点，最终要判断所有节点是否处于同一个连通分量中，DFS/BFS 是最直接的连通性检查工具。
• 并查集（Disjoint Set Union / Union-Find）：最优解使用 DSU 高效跟踪与合并连通分量，配合路径压缩和按大小合并（union by size），近常数时间完成合并与查询。
• 最大公约数（GCD）：理解欧几里得算法gcd(a, b) = gcd(b, a % b)，并能据此判断两个数是否共享公因数（gcd > 1）。
• 质因数分解：把数字拆成质因子，是"两个数是否共享因子"判断的高效替代方案——共享因子 ⇔ 共享至少一个质因子。
• 埃氏筛（Sieve of Eratosthenes）：预计算每个数的最小质因子（SPF），使每个数的分解从 O(√m) 降到 O(log m)，这是解法三、四、五的性能关键。

问题建模：把"共享公因数"翻译成"图的连通性"

题目要求判断：给定数组nums，是否存在一种遍历顺序，使得任意两个下标i、j之间都能通过"间接相连"到达？其中两个下标可以直接相连的条件是gcd(nums[i], nums[j]) > 1。

核心观察一：如果直接把每个下标当作一个节点、把满足gcd > 1的下标对连边，问题就等价于"整张图是否连通"。这是解法一（暴力 DFS）的直接思路。

核心观察二：gcd(a, b) > 1意味着a与b共享至少一个质因子。因此"下标之间是否连通"可以转换为"下标与其质因子之间是否连通"——两个下标只要都连接着同一个质因子节点，它们就在同一分量中。这一观察让解法二到五得以避开 O(n²) 的两两比较，将边数从 O(n²) 压缩到 O(n log m)。

两种建模方式的区别可以这样理解：

解法一：暴力 DFS（Brute Force）

直觉

两个下标可连通 ⇔ 它们对应的数值共享大于 1 的公因数。把每个下标作为一个节点，凡是gcd(nums[i], nums[j]) > 1的下标对之间连一条无向边，问题立刻退化为"判断图是否只有一个连通分量"。

算法步骤

1. 构建邻接表：遍历所有下标对(i, j)，若gcd(nums[i], nums[j]) > 1，则在adj[i]与adj[j]之间互相加边；
2. 从下标0出发执行 DFS，标记所有可达节点；
3. DFS 结束后，检查是否所有节点都被访问；
4. 若全部访问过返回true，否则返回false。

代码实现

class Solution: def canTraverseAllPairs(self, nums: List[int]) -> bool: n = len(nums) visit = [False] * n adj = [[] for _ in range(n)] for i in range(n): for j in range(i + 1, n): if gcd(nums[i], nums[j]) > 1: adj[i].append(j) adj[j].append(i) def dfs(node): visit[node] = True for nei in adj[node]: if not visit[nei]: dfs(nei) dfs(0) for node in visit: if not node: return False return True

class Solution { public: bool canTraverseAllPairs(vector<int>& nums) { int n = nums.size(); vector<bool> visit(n, false); vector<vector<int>> adj(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (__gcd(nums[i], nums[j]) > 1) { adj[i].push_back(j); adj[j].push_back(i); } } } dfs(0, adj, visit); for (bool node : visit) { if (!node) { return false; } } return true; } private: void dfs(int node, vector<vector<int>>& adj, vector<bool>& visit) { visit[node] = true; for (int& nei : adj[node]) { if (!visit[nei]) { dfs(nei, adj, visit); } } } };

本仓库的文章 articles/greatest-common-divisor-traversal.md 中还提供了 Java、JavaScript、C#、Go、Kotlin、Swift、Rust 版本的完整代码，实现思路完全一致。

时间复杂度与空间复杂度

• 时间复杂度：$O(n ^ 2 \log n)$——两层循环枚举所有下标对，每次调用gcd的代价为 O(log n)；
• 空间复杂度：$O(n ^ 2)$——邻接表在最坏情况下（所有数两两互质因子重叠）存储约 n²/2 条边。

局限：当 n 达到 10⁵ 量级时，O(n²) 的建图完全不可行，必须引入质因数分解来压缩边数。

解法二：并查集 + 试除质因数分解（Disjoint Set Union）

直觉

不再显式地在下标之间建边，而是通过质因子中转：两个数只要共享一个质因子，就应当处于同一连通分量。用并查集把每个下标与"该质因子第一次出现的下标"合并，即可完全避开 O(n²) 的两两比较。

算法步骤

1. 初始化一个包含n个元素的并查集；
2. 维护一个哈希表factor_index，记录"质因子 → 第一次出现该因子的下标"；
3. 对每个数用试除法（f从 2 试到 √num）做质因数分解；
4. 对分解出的每个质因子f：
   • 若f已出现过，将当前下标与factor_index[f]合并（union）；
   • 否则把factor_index[f]记为当前下标；
5. 分解完所有数后，检查所有下标是否同属一个连通分量。

代码实现

class UnionFind: def __init__(self, n): self.n = n self.Parent = list(range(n + 1)) self.Size = [1] * (n + 1) def find(self, node): if self.Parent[node] != node: self.Parent[node] = self.find(self.Parent[node]) return self.Parent[node] def union(self, u, v): pu = self.find(u) pv = self.find(v) if pu == pv: return False self.n -= 1 if self.Size[pu] < self.Size[pv]: pu, pv = pv, pu self.Size[pu] += self.Size[pv] self.Parent[pv] = pu return True def isConnected(self): return self.n == 1 class Solution: def canTraverseAllPairs(self, nums: List[int]) -> bool: uf = UnionFind(len(nums)) factor_index = {} # f -> index of value with factor f for i, n in enumerate(nums): f = 2 while f * f <= n: if n % f == 0: if f in factor_index: uf.union(i, factor_index[f]) else: factor_index[f] = i while n % f == 0: n = n // f f += 1 if n > 1: if n in factor_index: uf.union(i, factor_index[n]) else: factor_index[n] = i return uf.isConnected()

public class Solution { public boolean canTraverseAllPairs(int[] nums) { int n = nums.length; UnionFind uf = new UnionFind(n); Map<Integer, Integer> factorIndex = new HashMap<>(); for (int i = 0; i < n; i++) { int num = nums[i]; int f = 2; while (f * f <= num) { if (num % f == 0) { if (factorIndex.containsKey(f)) { uf.union(i, factorIndex.get(f)); } else { factorIndex.put(f, i); } while (num % f == 0) { num /= f; } } f++; } if (num > 1) { if (factorIndex.containsKey(num)) { uf.union(i, factorIndex.get(num)); } else { factorIndex.put(num, i); } } } return uf.isConnected(); } }

完整的多语言版本（C++ / JavaScript / C# / Go / Kotlin / Swift / Rust）同样收录在 articles/greatest-common-divisor-traversal.md。

仓库源码对照

本仓库的 python/2709-greatest-common-divisor-traversal.py 正是这一思路的工程化实现。与文档版本相比，它做了两处微调：

• find采用递归路径压缩，union采用按大小合并（size小的根挂到大的根下），保证平均复杂度接近反阿克曼函数 O(α(n))；
• 用count成员变量直接记录当前连通分量数量，每成功合并一次count -= 1，最终只要count == 1即说明整张图连通，无需再逐一下标查询根节点。

class UnionFind: def __init__(self, n): self.par = [i for i in range(n)] self.size = [1] * n self.count = n def find(self, x): if self.par[x] != x: self.par[x] = self.find(self.par[x]) return self.par[x] def union(self, x, y): px, py = self.find(x), self.find(y) if px == py: return if self.size[px] < self.size[py]: self.par[px] = py self.size[py] += self.size[px] else: self.par[py] = px self.size[px] += self.size[py] self.count -= 1

时间复杂度与空间复杂度

• 时间复杂度：$O(m + n\sqrt {m})$——每个数试除分解至多 O(√m)，并查集操作近似 O(1)；
• 空间复杂度：$O(n \log m)$——factor_index哈希表最多记录 n 个数各自去重后的质因子总数。

其中 $n$ 是数组nums的大小，$m$ 是数组中的最大值。

解法三：埃氏筛 SPF + 并查集（Sieve of Eratosthenes + DSU）

直觉

解法二的瓶颈在试除分解：每个数最坏 O(√m)。如果先用埃氏筛预计算每个数的最小质因子（SPF），就能在 O(log m) 时间内分解任意一个数。随后用并查集把每个下标直接连接到代表质因子的虚拟节点上，进一步简化"质因子 → 首次出现下标"的映射逻辑。

算法步骤

1. 处理边界：数组只有 1 个元素时直接返回true；数组中出现值1时直接返回false（1 没有任何大于 1 的质因子，永远无法与其他数相连）；
2. 构建筛数组sieve，其中sieve[x]保存x的最小质因子；
3. 初始化大小为n + MAX + 1的并查集（下标 0..n-1 + 虚拟质数节点）；
4. 对每个下标：用sieve分解其数值，对每个质因子prime执行uf.union(i, N + prime)；
5. 最后验证所有下标在并查集中拥有同一个根。

代码实现

class UnionFind: def __init__(self, n): self.Parent = list(range(n + 1)) self.Size = [1] * (n + 1) def find(self, node): if self.Parent[node] != node: self.Parent[node] = self.find(self.Parent[node]) return self.Parent[node] def union(self, u, v): pu = self.find(u) pv = self.find(v) if pu == pv: return False if self.Size[pu] < self.Size[pv]: pu, pv = pv, pu self.Size[pu] += self.Size[pv] self.Parent[pv] = pu return True class Solution: def canTraverseAllPairs(self, nums: List[int]) -> bool: N = len(nums) if N == 1: return True if any(num == 1 for num in nums): return False MAX = max(nums) sieve = [0] * (MAX + 1) p = 2 while p * p <= MAX: if sieve[p] == 0: for composite in range(p * p, MAX + 1, p): sieve[composite] = p p += 1 uf = UnionFind(N + MAX + 1) for i in range(N): num = nums[i] if sieve[num] == 0: # num is prime uf.union(i, N + num) continue while num > 1: prime = sieve[num] if sieve[num] != 0 else num uf.union(i, N + prime) while num % prime == 0: num //= prime root = uf.find(0) for i in range(1, N): if uf.find(i) != root: return False return True

class Solution { public: bool canTraverseAllPairs(vector<int>& nums) { int N = nums.size(); if (N == 1) { return true; } for (int num : nums) { if (num == 1) { return false; } } int MAX = *max_element(nums.begin(), nums.end()); vector<int> sieve(MAX + 1, 0); for (int p = 2; p * p <= MAX; p++) { if (sieve[p] == 0) { for (int composite = p * p; composite <= MAX; composite += p) { sieve[composite] = p; } } } UnionFind uf(N + MAX + 1); for (int i = 0; i < N; i++) { int num = nums[i]; if (sieve[num] == 0) { // num is prime uf.unionSet(i, N + num); continue; } while (num > 1) { int prime = sieve[num] != 0 ? sieve[num] : num; uf.unionSet(i, N + prime); while (num % prime == 0) { num /= prime; } } } int root = uf.find(0); for (int i = 1; i < N; i++) { if (uf.find(i) != root) { return false; } } return true; } };

其中UnionFind类与解法二的实现一致（路径压缩 + 按大小合并），Java、JavaScript、C#、Rust 版本见 articles/greatest-common-divisor-traversal.md。

实现细节说明：

• 虚拟质数节点的编号约定为N + prime：数组下标占0..N-1，质因子节点从N开始编号。这样既不会与下标冲突，又能在 O(1) 时间内由质因子算出节点编号；
• 当num本身是质数时，sieve[num] == 0，直接与N + num合并并跳过分解；
• 分解循环内用while (num % prime == 0) num /= prime把该质因子的所有幂次一次性除尽，避免重复合并。

时间复杂度与空间复杂度

• 时间复杂度：$O(m + n \log m)$——埃氏筛 O(m)，每个数用 SPF 分解 O(log m)；
• 空间复杂度：$O(n + m)$——筛数组 O(m) + 并查集 O(n + m)（含虚拟节点）。

其中 $n$ 是数组nums的大小，$m$ 是数组中的最大值。这也是本仓库 kotlin/2709-greatest-common-divisor-traversal.kt 采用的方向。

解法四：埃氏筛 + DFS（显式图）

直觉

不借助并查集，直接构建"下标 ↔ 质因子"的双向邻接表，再用一次 DFS 从下标0出发遍历全图。由于每个数至多有 O(log m) 个质因子，整张图的边数为 O(n log m)，DFS 一次即可判定连通性。

算法步骤

1. 处理边界：单元素返回true；存在值1返回false；
2. 构建最小质因子筛数组；
3. 构建邻接表：每个下标i与它的每个质因子节点N + prime互相连边；
4. 从下标0出发 DFS，访问所有可达节点；
5. 若下标0..N-1全部被访问则返回true，否则false。

代码实现

class Solution: def canTraverseAllPairs(self, nums: List[int]) -> bool: N = len(nums) if N == 1: return True if any(num == 1 for num in nums): return False MAX = max(nums) sieve = [0] * (MAX + 1) p = 2 while p * p <= MAX: if sieve[p] == 0: for composite in range(p * p, MAX + 1, p): sieve[composite] = p p += 1 adj = defaultdict(list) for i in range(N): num = nums[i] if sieve[num] == 0: # num is prime adj[i].append(N + num) adj[N + num].append(i) continue while num > 1: prime = sieve[num] if sieve[num] != 0 else num adj[i].append(N + prime) adj[N + prime].append(i) while num % prime == 0: num //= prime visited = set() def dfs(node): visited.add(node) for nei in adj[node]: if nei not in visited: dfs(nei) dfs(0) for i in range(N): if i not in visited: return False return True

class Solution { /** * @param {number[]} nums * @return {boolean} */ canTraverseAllPairs(nums) { const N = nums.length; if (N === 1) return true; if (nums.includes(1)) return false; const MAX = Math.max(...nums); const sieve = new Array(MAX + 1).fill(0); for (let p = 2; p * p <= MAX; p++) { if (sieve[p] === 0) { for (let composite = p * p; composite <= MAX; composite += p) { sieve[composite] = p; } } } const adj = new Map(); for (let i = 0; i < N; i++) { if (!adj.has(i)) adj.set(i, []); let num = nums[i]; if (sieve[num] === 0) { if (!adj.has(N + num)) adj.set(N + num, []); adj.get(i).push(N + num); adj.get(N + num).push(i); continue; } while (num > 1) { const prime = sieve[num] === 0 ? num : sieve[num]; if (!adj.has(N + prime)) adj.set(N + prime, []); adj.get(i).push(N + prime); adj.get(N + prime).push(i); while (num % prime === 0) num = Math.floor(num / prime); } } const visited = new Set(); const dfs = (node) => { visited.add(node); for (const neighbor of adj.get(node) || []) { if (!visited.has(neighbor)) { dfs(neighbor); } } }; dfs(0); for (let i = 0; i < N; i++) { if (!visited.has(i)) return false; } return true; } }

Java、C++、C#、Rust 版本见 articles/greatest-common-divisor-traversal.md。注意 C# / Rust 等语言用AddEdge/entry辅助方法处理双向加边，避免漏建任一方向的邻接关系。

时间复杂度与空间复杂度

• 时间复杂度：$O(m + n \log m)$；
• 空间复杂度：$O(n + m)$——邻接表边数 O(n log m)，加上筛数组 O(m)。

解法五：埃氏筛 + BFS

直觉

BFS 是 DFS 的迭代替代方案，适合显式用队列进行连通性遍历。图的构建方式与解法四完全相同，只是把递归 DFS 换成显式队列，从下标0开始逐层扩散。

算法步骤

1. 处理边界：单元素返回true；存在值1返回false；
2. 构建最小质因子筛数组；
3. 构建"下标 ↔ 质因子（偏移N）"的双向邻接表；
4. 队列初始化为[0]，visited集合加入0；
5. BFS 处理队列：弹出节点，把所有未访问邻居入队并标记；
6. 若下标0..N-1全部访问过则返回true，否则false。

代码实现

class Solution: def canTraverseAllPairs(self, nums: List[int]) -> bool: N = len(nums) if N == 1: return True if any(num == 1 for num in nums): return False MAX = max(nums) sieve = [0] * (MAX + 1) p = 2 while p * p <= MAX: if sieve[p] == 0: for composite in range(p * p, MAX + 1, p): sieve[composite] = p p += 1 adj = defaultdict(list) for i in range(N): num = nums[i] if sieve[num] == 0: # num is prime adj[i].append(N + num) adj[N + num].append(i) continue while num > 1: prime = sieve[num] if sieve[num] != 0 else num adj[i].append(N + prime) adj[N + prime].append(i) while num % prime == 0: num //= prime visited = set() queue = deque([0]) visited.add(0) while queue: node = queue.popleft() for nei in adj[node]: if nei not in visited: visited.add(nei) queue.append(nei) for i in range(N): if i not in visited: return False return True

func canTraverseAllPairs(nums []int) bool { n := len(nums) if n == 1 { return true } for _, v := range nums { if v == 1 { return false } } MAX := 0 for _, v := range nums { if v > MAX { MAX = v } } sieve := make([]int, MAX+1) for p := 2; p*p <= MAX; p++ { if sieve[p] == 0 { for c := p * p; c <= MAX; c += p { sieve[c] = p } } } adj := make(map[int][]int) for i := 0; i < n; i++ { num := nums[i] if sieve[num] == 0 { adj[i] = append(adj[i], n+num) adj[n+num] = append(adj[n+num], i) continue } for num > 1 { prime := sieve[num] if prime == 0 { prime = num } adj[i] = append(adj[i], n+prime) adj[n+prime] = append(adj[n+prime], i) for num%prime == 0 { num /= prime } } } visited := make(map[int]bool) q := []int{0} visited[0] = true for len(q) > 0 { node := q[0] q = q[1:] for _, nei := range adj[node] { if !visited[nei] { visited[nei] = true q = append(q, nei) } } } for i := 0; i < n; i++ { if !visited[i] { return false } } return true }

Java、C++、JavaScript、C#、Rust 版本见 articles/greatest-common-divisor-traversal.md。

时间复杂度与空间复杂度

• 时间复杂度：$O(m + n \log m)$；
• 空间复杂度：$O(n + m)$。

五种解法对比一览

选型建议：

• 面试中最稳妥、最容易讲清楚的是解法三（埃氏筛 + DSU）：它同时体现了数论（筛法）与图论（并查集）两个考点，代码量适中，且复杂度达到最优；
• 如果允许 O(n²) 且 n 较小（如 n ≤ 10³），解法一用于"快速验证正确性"非常直观；
• 解法二适合面试官追问"如何不建图解决"，展示对factor_index映射的精妙运用；
• 解法四、五展示同一图模型的两种遍历实现，可作为"DFS/BFS 皆可"的延伸讨论点。

常见陷阱与边界情况

陷阱一：没有把值 1 作为特例处理

数字 1 没有任何大于 1 的质因子，无法与任何其他数共享公因数。因此只要数组长度大于 1 且包含 1，答案必定是false。若不提前处理，试除分解循环while f * f <= n会直接跳过，导致 1 永远孤立，而某些实现甚至可能陷入死循环。

陷阱二：忘记单元素情况

数组只有一个元素时，没有任何"对"需要检查，应当直接返回true（无论该元素是什么值）。如果分解或并查集逻辑假设至少有两个元素，就会在nums = [1]这类用例上出错。

陷阱三：质因数分解不彻底

分解时必须把每个质因子的所有幂次完全除尽再处理下一个因子。常见的 bug 是：找到因子f后只除一次就f++，导致同一个质因子被重复合并（重复 union 虽不破坏正确性但浪费）或漏掉幂次产生错误因子集合。正确写法是内层while (num % prime == 0) num /= prime;。

陷阱四：虚拟质数节点的 off-by-one 错误

使用虚拟节点时，数组下标范围是0..N-1，质因子节点编号是N + prime。常见的错误包括：忘记加偏移N直接使用质因子本身作为节点号，或在不同解法之间混用偏移约定，导致"本应连通的两个下标"查询出不同根，产生假阴性结果。

陷阱五：大质数导致的内存问题

当数组中最大值m达到 10⁵ 甚至 10⁶ 量级时，按最大值分配数组会消耗显著内存。务必把并查集与筛数组的尺寸统一规划为N + MAX + 1（覆盖 n 个下标 + MAX 范围内的虚拟质数节点），避免越界访问。若使用解法二（无筛数组），则内存开销主要来自factor_index哈希表，通常更省。

仓库中的工程化实现与延伸阅读

本题在仓库中的源码

• python/2709-greatest-common-divisor-traversal.py：解法二的工程化版本，UnionFind类内聚了路径压缩、按大小合并与count计数，主流程用factor_index哈希表完成质因子到下标的映射；
• kotlin/2709-greatest-common-divisor-traversal.kt：Kotlin 版本实现；
• 完整多语言题解与五种解法的逐步推导见 articles/greatest-common-divisor-traversal.md。

数论与并查集的关联题目

如果你希望把本题涉及的技能点迁移到更多题目，仓库内这些文档可以构成一条完整的学习路径：

• GCD 相关：articles/greatest-common-divisor-of-strings.md（字符串 GCD）、articles/insert-greatest-common-divisors-in-linked-list.md（链表 GCD 插入）；
• 筛法相关：articles/count-primes.md（埃氏筛统计质数数量）；
• 并查集连通性：articles/count-connected-components.md、articles/number-of-provinces.md、articles/redundant-connection.md（无向图判环）、articles/valid-tree.md（树结构验证）；
• 图遍历判定连通性：articles/course-schedule.md（拓扑排序思想）。

这些文章与本题共享同一套"建模 → 选数据结构 → 边界处理 → 复杂度论证"的分析框架，非常适合对比阅读。

小结

Greatest Common Divisor Traversal 是一道把**数论（GCD、质因数分解、埃氏筛）与图论（连通性、DFS/BFS、并查集）**深度融合的经典题目。解题的关键跃迁在于：不要在下标之间两两建边，而是通过质因子做中转，把"共享因子"关系压缩成"下标—质因子"的稀疏二分结构，从而把 O(n²) 的暴力复杂度优化到 O(m + n log m)。无论最终选择 DSU 还是显式图 + 遍历，都必须牢牢守住两个边界特例：单元素数组返回true、包含值 1 返回false，并确保虚拟节点偏移与分解循环的正确性。掌握了这五种解法与对应陷阱，你就能在本仓库的多语言实现中游刃有余地对照、复现与迁移这套模板。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode