You are given an integer n
. There is an undirected graph with n
nodes, numbered from 0
to n - 1
. You are given a 2D integer array edges
where edges[i] = [ai, bi]
denotes that there exists an undirected edge connecting nodes ai
and bi
.
Return the number of pairs of different nodes that are unreachable from each other.
Example 1:

Input: n = 3, edges = [[0,1],[0,2],[1,2]] Output: 0 Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.
Example 2:

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]] Output: 14 Explanation: There are 14 pairs of nodes that are unreachable from each other: [[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]. Therefore, we return 14.
Constraints:
1 <= n <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
- There are no repeated edges.
Solution 1: DFS
Use DFS to find all CCs
Time complexity: O(V+E)
Space complexity: O(V+E)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Author: Huahua, 791ms, 136 MB class Solution { public: long long countPairs(int n, vector<vector<int>>& edges) { vector<vector<int>> g(n); for (const auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); } vector<int> seen(n); long long cur = 0; function<void(int)> dfs = [&](int u) { ++cur; for (int v : g[u]) if (seen[v]++ == 0) dfs(v); }; long long ans = 0; for (int i = 0; i < n; ++i) { if (seen[i]++) continue; cur = 0; dfs(i); ans += (n - cur) * cur; } return ans / 2; } }; |
Solution 2: Union Find
Time complexity: O(V+E)
Space complexity: O(V)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua class Solution { public: long long countPairs(int n, vector<vector<int>>& edges) { vector<int> parents(n); vector<int> counts(n, 1); std::iota(begin(parents), end(parents), 0); function<int(int)> find = [&](int x) { if (parents[x] == x) return x; return parents[x] = find(parents[x]); }; for (const auto& e : edges) { int ru = find(e[0]); int rv = find(e[1]); if (ru != rv) { parents[rv] = ru; counts[ru] += counts[rv]; } } long long ans = 0; for (int i = 0; i < n; ++i) ans += n - counts[find(i)]; return ans / 2; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment