HardRating 2457
1782. Count Pairs Of Nodes
arrayhash-tabletwo-pointersbinary-searchgraphsortingcounting
解題說明
Count Pairs Of Nodes
題目描述：給定一個無向圖和多個查詢，每個查詢給出一個整數值。定義 incident(a, b) = degree(a) + degree(b) - edge_count(a, b)，即兩節點的度數之和減去它們之間的邊數（含重邊）。對每個查詢 q，計算滿足 incident(a, b) > q 的節點對 (a, b) 數量。
解題思路：先計算每個節點的度數，將度數排序後用雙指標快速計算 degree[a] + degree[b] > q 的配對數。但這會過度計算，因為有些配對的邊數需要扣除。對於有邊直接相連的節點對 (u, v)，若 degree[u] + degree[v] > q 但 degree[u] + degree[v] - edge_count(u,v) <= q，則需要從結果中減去。只需遍歷所有實際存在的邊來修正。
C++ 解法
複雜度分析
時間複雜度：O(n log n + Q × (n + E')) — 排序 O(n log n)，每個查詢雙指標 O(n) 加上修正 O(E')，E' 為不同邊的數量。
空間複雜度：O(n + E') — 度數陣列和邊計數 map。
虛擬碼
1. Compute degree of each node and count of each edge (u,v) pair
2. Sort degrees
3. For each query q:
a. Two pointers on sorted degrees: count pairs where deg[lo] + deg[hi] > q
b. For each distinct edge (u,v) with count c:
- If degree[u] + degree[v] > q but degree[u] + degree[v] - c <= q: count--
c. Append count to answer
4. Return answer其他解法
暴力枚舉 O(n^2)：直接枚舉所有節點對計算 incident 值。簡單但 n 達 2×10^4 時不可行。
二分搜索：排序度數後，對每個節點用二分搜索找到配對閾值，再修正。時間與雙指標相同，但二分搜索版本更容易推廣到其他查詢模式。
延伸思考
- 若圖是有向的，incident 的定義如何調整？
- 若邊帶有權重，incident 計算方式如何修改？
- 若要支援動態新增邊並即時回答查詢，資料結構該如何設計？