HardRating 2272

952. Largest Component Size by Common Factor

arrayhash-tablemathunion-findnumber-theory

在 LeetCode 上作答 ↗

解題說明

Largest Component Size by Common Factor

題目描述：給定一個正整數陣列 nums，如果 nums[i] 和 nums[j] 有大於 1 的公因數，就在它們之間連一條邊。求最大連通分量的大小。

解題思路：

Union-Find + 質因數分解：對每個數字做質因數分解。如果兩個數字共享一個質因數，它們就在同一個連通分量中。
對每個數字 nums[i]，找出其所有質因數。將 nums[i] 與每個質因數合併（Union）。
共享質因數的數字會通過該質因數間接地被合併到同一個集合。
最後統計每個集合中包含多少個原始數字（非質因數），取最大值。
關鍵優化：不直接對數字配對（O(n^2)），而是通過質因數作為中間節點進行合併。

C++ 解法

複雜度分析

時間複雜度：O(n * sqrt(M) * α(M)) — n 為陣列長度，M 為最大值。每個數字的質因數分解 O(sqrt(M))，Union-Find 操作近乎 O(1)

空間複雜度：O(M) — Union-Find 陣列大小為最大值 M

虛擬碼

1. Initialize Union-Find with size = max(nums) + 1
2. For each number in nums:
   a. Find all prime factors by trial division up to sqrt(num)
   b. Unite(num, factor) for each prime factor
   c. Also unite(num, num/factor) for the complementary factor
3. Count how many nums share the same root in Union-Find
4. Return the maximum count

其他解法

Sieve + Union-Find：用類似埃拉托斯特尼篩法的方式，對每個質數 p，將所有陣列中 p 的倍數合併。避免了逐個質因數分解的開銷。
建圖 + DFS/BFS：顯式地對共享因數的數字建邊，然後用 DFS/BFS 找連通分量。但建邊可能需要 O(n^2) 時間，且邊數可能爆炸。

延伸思考

如果不是「有公因數」而是「互質」時才連邊，最大連通分量的大小是多少？
如何高效地動態增加或刪除數字，並維護最大連通分量？
如果改為有向圖（a 的所有因數都有邊指向 a），最長路徑是多少？

Largest Component Size by Common Factor — CaffeCode