Count Unreachable Pairs of Nodes in an Undirected Graph

解題說明

Count Unreachable Pairs of Nodes in an Undirected Graph

題目描述：給定 n 個節點的無向圖和一組邊，計算有多少對節點彼此不可達（即不在同一個連通分量中）。

解題思路：使用 Union-Find（並查集）找出所有連通分量及其大小。若連通分量的大小分別為 s1, s2, ..., sk，則不可達的節點對數量為所有不同分量之間的節點配對數。

計算方式：遍歷每個連通分量，對於大小為 si 的分量，它與所有其他分量的節點配對數為 si * (n - si)。由於每對會被計算兩次，最終答案除以 2。或者等價地，可以累計已遍歷的節點數，每次加上 si * (已遍歷節點數)。

1. Initialize Union-Find with n nodes 2. For each edge (u, v), union u and v 3. Count size of each connected component 4. Initialize answer = 0, seen = 0 5. For each component of size s: a. answer += s * seen b. seen += s 6. Return answer

其他解法

DFS/BFS 連通分量法：建立鄰接表，用 DFS 或 BFS 找出所有連通分量的大小。時間複雜度同為 O(n + E)，空間需要鄰接表 O(n + E)。比 Union-Find 佔用更多記憶體但更直觀。
數學公式法：總配對數為 n*(n-1)/2，減去同一分量內的配對數 Σ si*(si-1)/2 即為答案。本質相同但計算方式不同。

延伸思考

如果圖是有向圖，如何計算不可達的有序節點對數量？（提示：強連通分量）
如果動態新增邊，每次新增後需要更新不可達對數，如何高效處理？
如果要找出所有不可達對中距離最短的一對（假設加一條邊後可達），如何設計演算法？

解題說明