HardRating 2300

1697. Checking Existence of Edge Length Limited Paths

arraytwo-pointersunion-findgraphsorting

解題說明

Checking Existence of Edge Length Limited Paths

題目描述：給定一個無向加權圖和多個查詢 queries[i] = [p, q, limit]，對每個查詢判斷從節點 p 到節點 q 是否存在一條路徑，使路徑上每條邊的權重都嚴格小於 limit。

解題思路：離線處理 — 將邊按權重排序，將查詢按 limit 排序。使用 Union-Find 資料結構，依序處理查詢：對於 limit 值遞增的查詢，逐步將權重小於當前 limit 的邊加入 Union-Find。查詢 p 和 q 是否連通只需檢查它們是否在同一集合。這樣每條邊只被處理一次，整體效率極高。

C++ 解法

複雜度分析

時間複雜度：O((E + Q) log(E + Q) + (E + Q) × α(n)) — 排序邊和查詢為主要開銷，Union-Find 操作近乎 O(1)（α 為反阿克曼函數）。

空間複雜度：O(n + Q) — Union-Find 陣列 O(n)，索引陣列 O(Q)。

虛擬碼

1. Initialize Union-Find with n nodes
2. Sort edges by weight ascending
3. Create query index array, sort by limit ascending
4. Set edge pointer ei = 0
5. For each query index qi (in sorted order):
   a. While ei < |edges| and edges[ei].weight < queries[qi].limit:
      - Union(edges[ei].u, edges[ei].v), ei++
   b. ans[qi] = (Find(queries[qi].p) == Find(queries[qi].q))
6. Return ans

其他解法

在線 BFS/DFS：對每個查詢建立一個只包含權重 < limit 的邊的子圖，然後做 BFS/DFS 檢查連通性。時間 O(Q × (V + E))，適合查詢少的情況，但大量查詢時極慢。

Kruskal 最小瓶頸路徑樹：建立最小生成樹後，兩點間路徑上的最大邊權即為瓶頸距離。查詢變成樹上路徑最大值查詢，可用 LCA + 倍增法做到 O(log n) 每次查詢，但實作複雜度高。

延伸思考

若查詢必須在線處理（不能離線排序），如何設計？
若圖是動態的（邊會被新增或刪除），如何維護查詢結果？
若要回傳滿足條件的最短路徑長度（而非僅判斷連通），該如何修改？

Checking Existence of Edge Length Limited Paths — CaffeCode