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 的路径压缩与按秩合并写法、SPFSmallest 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)。两种建模方式的区别可以这样理解建模方式节点边边数直接建图n 个下标gcd(nums[i], nums[j]) 1的下标对最坏 O(n²)质因子中转n 个下标 若干质因子下标 ↔ 其质因子O(n log m)解法一暴力 DFSBrute Force直觉两个下标可连通 ⇔ 它们对应的数值共享大于 1 的公因数。把每个下标作为一个节点凡是gcd(nums[i], nums[j]) 1的下标对之间连一条无向边问题立刻退化为判断图是否只有一个连通分量。算法步骤构建邻接表遍历所有下标对(i, j)若gcd(nums[i], nums[j]) 1则在adj[i]与adj[j]之间互相加边从下标0出发执行 DFS标记所有可达节点DFS 结束后检查是否所有节点都被访问若全部访问过返回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 Trueclass Solution { public: bool canTraverseAllPairs(vectorint nums) { int n nums.size(); vectorbool visit(n, false); vectorvectorint 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, vectorvectorint adj, vectorbool 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²) 的两两比较。算法步骤初始化一个包含n个元素的并查集维护一个哈希表factor_index记录质因子 → 第一次出现该因子的下标对每个数用试除法f从 2 试到 √num做质因数分解对分解出的每个质因子f若f已出现过将当前下标与factor_index[f]合并union否则把factor_index[f]记为当前下标分解完所有数后检查所有下标是否同属一个连通分量。代码实现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); MapInteger, 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 个元素时直接返回true数组中出现值1时直接返回false1 没有任何大于 1 的质因子永远无法与其他数相连构建筛数组sieve其中sieve[x]保存x的最小质因子初始化大小为n MAX 1的并查集下标 0..n-1 虚拟质数节点对每个下标用sieve分解其数值对每个质因子prime执行uf.union(i, N prime)最后验证所有下标在并查集中拥有同一个根。代码实现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 Trueclass Solution { public: bool canTraverseAllPairs(vectorint 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()); vectorint 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 一次即可判定连通性。算法步骤处理边界单元素返回true存在值1返回false构建最小质因子筛数组构建邻接表每个下标i与它的每个质因子节点N prime互相连边从下标0出发 DFS访问所有可达节点若下标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 Trueclass 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开始逐层扩散。算法步骤处理边界单元素返回true存在值1返回false构建最小质因子筛数组构建下标 ↔ 质因子偏移N的双向邻接表队列初始化为[0]visited集合加入0BFS 处理队列弹出节点把所有未访问邻居入队并标记若下标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 Truefunc 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, MAX1) 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], nnum) adj[nnum] append(adj[nnum], i) continue } for num 1 { prime : sieve[num] if prime 0 { prime num } adj[i] append(adj[i], nprime) adj[nprime] append(adj[nprime], 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)$。五种解法对比一览解法建模方式分解方式时间空间核心数据结构1. 暴力 DFS下标对直接连边无需分解$O(n ^ 2 \log n)$$O(n ^ 2)$邻接表 递归 DFS2. 并查集 试除质因子 → 首次下标试除 O(√m)$O(m n\sqrt {m})$$O(n \log m)$DSU factor_index哈希表3. 埃氏筛 DSU下标 ↔ 虚拟质数节点SPF O(log m)$O(m n \log m)$$O(n m)$SPF 筛 DSUNMAX1 节点4. 埃氏筛 DFS下标 ↔ 虚拟质数节点SPF O(log m)$O(m n \log m)$$O(n m)$SPF 筛 邻接表 递归 DFS5. 埃氏筛 BFS下标 ↔ 虚拟质数节点SPF O(log m)$O(m n \log m)$$O(n m)$SPF 筛 邻接表 显式队列选型建议面试中最稳妥、最容易讲清楚的是解法三埃氏筛 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.ktKotlin 版本实现完整多语言题解与五种解法的逐步推导见 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 2709 Greatest Common Divisor Traversal 全解：五种解法从暴力 DFS 到埃氏筛优化（并查集与图论实战）
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 的路径压缩与按秩合并写法、SPFSmallest 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)。两种建模方式的区别可以这样理解建模方式节点边边数直接建图n 个下标gcd(nums[i], nums[j]) 1的下标对最坏 O(n²)质因子中转n 个下标 若干质因子下标 ↔ 其质因子O(n log m)解法一暴力 DFSBrute Force直觉两个下标可连通 ⇔ 它们对应的数值共享大于 1 的公因数。把每个下标作为一个节点凡是gcd(nums[i], nums[j]) 1的下标对之间连一条无向边问题立刻退化为判断图是否只有一个连通分量。算法步骤构建邻接表遍历所有下标对(i, j)若gcd(nums[i], nums[j]) 1则在adj[i]与adj[j]之间互相加边从下标0出发执行 DFS标记所有可达节点DFS 结束后检查是否所有节点都被访问若全部访问过返回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 Trueclass Solution { public: bool canTraverseAllPairs(vectorint nums) { int n nums.size(); vectorbool visit(n, false); vectorvectorint 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, vectorvectorint adj, vectorbool 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²) 的两两比较。算法步骤初始化一个包含n个元素的并查集维护一个哈希表factor_index记录质因子 → 第一次出现该因子的下标对每个数用试除法f从 2 试到 √num做质因数分解对分解出的每个质因子f若f已出现过将当前下标与factor_index[f]合并union否则把factor_index[f]记为当前下标分解完所有数后检查所有下标是否同属一个连通分量。代码实现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); MapInteger, 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 个元素时直接返回true数组中出现值1时直接返回false1 没有任何大于 1 的质因子永远无法与其他数相连构建筛数组sieve其中sieve[x]保存x的最小质因子初始化大小为n MAX 1的并查集下标 0..n-1 虚拟质数节点对每个下标用sieve分解其数值对每个质因子prime执行uf.union(i, N prime)最后验证所有下标在并查集中拥有同一个根。代码实现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 Trueclass Solution { public: bool canTraverseAllPairs(vectorint 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()); vectorint 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 一次即可判定连通性。算法步骤处理边界单元素返回true存在值1返回false构建最小质因子筛数组构建邻接表每个下标i与它的每个质因子节点N prime互相连边从下标0出发 DFS访问所有可达节点若下标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 Trueclass 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开始逐层扩散。算法步骤处理边界单元素返回true存在值1返回false构建最小质因子筛数组构建下标 ↔ 质因子偏移N的双向邻接表队列初始化为[0]visited集合加入0BFS 处理队列弹出节点把所有未访问邻居入队并标记若下标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 Truefunc 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, MAX1) 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], nnum) adj[nnum] append(adj[nnum], i) continue } for num 1 { prime : sieve[num] if prime 0 { prime num } adj[i] append(adj[i], nprime) adj[nprime] append(adj[nprime], 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)$。五种解法对比一览解法建模方式分解方式时间空间核心数据结构1. 暴力 DFS下标对直接连边无需分解$O(n ^ 2 \log n)$$O(n ^ 2)$邻接表 递归 DFS2. 并查集 试除质因子 → 首次下标试除 O(√m)$O(m n\sqrt {m})$$O(n \log m)$DSU factor_index哈希表3. 埃氏筛 DSU下标 ↔ 虚拟质数节点SPF O(log m)$O(m n \log m)$$O(n m)$SPF 筛 DSUNMAX1 节点4. 埃氏筛 DFS下标 ↔ 虚拟质数节点SPF O(log m)$O(m n \log m)$$O(n m)$SPF 筛 邻接表 递归 DFS5. 埃氏筛 BFS下标 ↔ 虚拟质数节点SPF O(log m)$O(m n \log m)$$O(n m)$SPF 筛 邻接表 显式队列选型建议面试中最稳妥、最容易讲清楚的是解法三埃氏筛 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.ktKotlin 版本实现完整多语言题解与五种解法的逐步推导见 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考