HardRating 2221
1627. Graph Connectivity With Threshold
arraymathunion-findnumber-theory
解題說明
Graph Connectivity With Threshold
題目描述: 有 n 個城市(編號 1 到 n)。兩個城市 a 和 b 之間存在道路,當且僅當存在一個大於 threshold 的整數 z,使得 z 同時整除 a 和 b(即 z 是 a 和 b 的公因數)。給定若干查詢 [a, b],判斷 a 和 b 是否連通。
解題思路: 使用並查集(Union-Find)。對每個大於 threshold 的整數 z,將 z 的所有倍數合併到同一個集合。具體地,遍歷 z 從 threshold+1 到 n,將 z, 2z, 3z, ... 依次合併。這樣,有公因數 > threshold 的城市自然會在同一個集合中。每次查詢只需判斷 find(a) == find(b)。
C++ 解法
複雜度分析
時間複雜度:O(n log n × alpha(n) + Q × alpha(n)) — 建圖的外層迴圈為調和級數 O(n log n),每次 union 操作 O(alpha(n)),Q 次查詢各 O(alpha(n))
空間複雜度:O(n) — 並查集的 parent 和 rank 陣列
虛擬碼
1. Initialize Union-Find with n+1 nodes
2. For z from threshold+1 to n:
a. For each multiple mult = 2z, 3z, ... up to n:
- Unite(z, mult)
3. For each query [a, b]:
a. Answer true if find(a) == find(b), else false
4. Return results其他解法
方法二:GCD 暴力檢查 對每對城市計算 gcd(a, b),如果 gcd > threshold 則連邊,然後用 BFS/DFS 或並查集判斷連通性。時間複雜度 O(n^2 log n),對於大 n 不可行。
方法三:篩法(Sieve)+ BFS 類似質因數篩法,先找出每個數的因數,然後建立鄰接表再 BFS。時間複雜度與本解法類似但實現較複雜。
延伸思考
- 如果 threshold 是 0,問題會簡化成什麼?所有城市都會連通嗎?
- 這個問題中的 union 操作和埃拉托斯特尼篩法(Sieve of Eratosthenes)有什麼結構上的相似之處?
- 如果查詢是動態的(threshold 會改變),如何有效地更新連通性?