济南知名网站建设平台百度经验官网登录

题目链接

Leetcode.2316 统计无向图中无法互相到达点对数 rating : 1604

题目描述

给你一个整数 $n$ ，表示一张 无向图 中有 $n$ 个节点，编号为 $0$ 到 $n-1$ 。同时给你一个二维整数数组 $edges$ ，其中 $edges[i]=[a_i,b_i]$ 表示节点 $a_i$ 和 $b_i$ 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

示例 2：

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[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]]
所以我们返回 14 。

提示：

• $1\le n\le 10^5$
• $0\le edges.length\le 2\ast 10^5$
• $edges[i].length=2$
• $0\le a_i,b_i<n$
• $a_i\ne b_i$
• 不会有重复边。

解法：dfs

无法到达的点对，假设其分别为 $a$ 和 $b$ ，那么这两个点一定是 不可达 的，说明两个点一定是在不同的 连通块。

所以我们第一步就要求出所有的 连通块 以及 连通块中的节点数量。

如上图，$3$ 个连通块，节点数量分别为 : $2,3,4$。

如果我们要 不重不漏 的计算所有 点对数，可以从左到右的计算：

• 对于 第一个连通块，它的右侧有两个连通块，节点数量分别是 $3,4$ 与它进行配对，所以一共有 $2\times (3+4)=14$；
• 对于 第二个连通块，它的右侧有一个连通块，节点数量是 $4$ 与它进行配对，所以一共有 $3\times 4=12$；

所以一共有 $14+12=26$ 个点对。

时间复杂度：$O(n)$

C++代码：

using LL = long long;class Solution {
public:long long countPairs(int n, vector<vector<int>>& edges) {vector<vector<int>> g(n);for(auto &e:edges){int a = e[0] , b = e[1];g[a].push_back(b);g[b].push_back(a);}int f[n];memset(f,-1,sizeof f);function<int(int)> dfs = [&](int u) ->int{int ans = 1;f[u] = 1;for(auto v:g[u]){if(f[v] != -1) continue;ans += dfs(v);}return ans;};vector<int> vec;for(int i = 0;i < n;i++){if(f[i] == 1) continue;int x = dfs(i);vec.push_back(x); }LL ans = 0;for(int i = 0;i < vec.size() - 1;i++){n -= vec[i];ans += vec[i] * 1LL * n;}return ans;}
};