MediumRating 1659

3532. Path Existence Queries in a Graph I

arrayhash-tablebinary-searchunion-findgraph

解題說明

Path Existence Queries in a Graph I

題目描述：給定 n 個節點（編號 0 到 n-1）和一個整數 maxDiff。若兩個節點 i 和 j 滿足 |nums[i] - nums[j]| <= maxDiff，則它們之間有一條邊。給定多個查詢 [u, v]，判斷節點 u 和 v 是否連通。

解題思路：關鍵觀察：若將節點按 nums 值排序，節點 i 和 j 相連的條件是 |nums[i] - nums[j]| <= maxDiff。排序後，連通分量就是排序陣列中相鄰元素差值不超過 maxDiff 的連續段。因此只需要找到每個「斷點」（相鄰差值 > maxDiff 的位置），同一段內的節點互相連通。對每個查詢，判斷 u 和 v 的排序位置是否在同一段中即可。

C++ 解法

複雜度分析

時間複雜度：O(n log n + q) — 排序 O(n log n)，分配連通分量 O(n)，處理 q 個查詢各 O(1)。

空間複雜度：O(n) — 儲存排序索引和分量編號。

虛擬碼

1. Create index array [0, 1, ..., n-1], sort by nums[idx]
2. Scan sorted indices: assign component IDs
   - Start with compId = 0
   - For each consecutive pair in sorted order: if nums difference > maxDiff, increment compId
   - comp[idx[i]] = compId
3. For each query [u, v]: answer true if comp[u] == comp[v]
4. Return results

其他解法

Union-Find 直接建圖：排序後，將相鄰差值 <= maxDiff 的節點 union 起來。時間複雜度相同 O(n log n)，但 Union-Find 有額外常數開銷。

暴力 BFS/DFS：對每個查詢從 u 開始搜尋是否能到達 v。最差 O(q * n²)，在大資料下會超時。

延伸思考

如果 maxDiff 不固定，每個查詢有自己的 maxDiff 值，如何高效處理？（提示：離線排序 + 逐步合併）
如果節點的 nums 值可以動態更新，如何維護連通分量？
若改為有向圖（只有 nums[i] < nums[j] 時才有 i→j 的邊），如何判斷可達性？

Path Existence Queries in a Graph I — CaffeCode