网站中数据查询如何做,你有网站 我做房东 只收佣金的网站,惠阳惠州网站建设,百度seo关键词工具题目链接 Leetcode.2316 统计无向图中无法互相到达点对数 rating : 1604 题目描述
给你一个整数 n n n #xff0c;表示一张 无向图 中有 n n n 个节点#xff0c;编号为 0 0 0 到 n − 1 n - 1 n−1 。同时给你一个二维整数数组 e d g e s edges edges #xff0c;其…题目链接 Leetcode.2316 统计无向图中无法互相到达点对数 rating : 1604 题目描述
给你一个整数 n n n 表示一张 无向图 中有 n n n 个节点编号为 0 0 0 到 n − 1 n - 1 n−1 。同时给你一个二维整数数组 e d g e s edges edges 其中 e d g e s [ i ] [ a i , b i ] edges[i] [a_i, b_i] edges[i][ai,bi] 表示节点 a i a_i ai 和 b i b_i bi 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。
示例 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 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105 0 ≤ e d g e s . l e n g t h ≤ 2 ∗ 1 0 5 0 \leq edges.length \leq 2 * 10^5 0≤edges.length≤2∗105 e d g e s [ i ] . l e n g t h 2 edges[i].length 2 edges[i].length2 0 ≤ a i , b i n 0 \leq a_i, b_i n 0≤ai,bin a i ≠ b i a_i \neq b_i aibi不会有重复边。
解法dfs
无法到达的点对假设其分别为 a a a 和 b b b 那么这两个点一定是 不可达 的说明两个点一定是在不同的 连通块。
所以我们第一步就要求出所有的 连通块 以及 连通块中的节点数量。 如上图 3 3 3 个连通块节点数量分别为 : 2 , 3 , 4 2 , 3 ,4 2,3,4。
如果我们要 不重不漏 的计算所有 点对数可以从左到右的计算
对于 第一个连通块它的右侧有两个连通块节点数量分别是 3 , 4 3,4 3,4 与它进行配对所以一共有 2 × ( 3 4 ) 14 2 \times (34) 14 2×(34)14对于 第二个连通块它的右侧有一个连通块节点数量是 4 4 4 与它进行配对所以一共有 3 × 4 12 3 \times 4 12 3×412
所以一共有 14 12 26 14 12 26 141226 个点对。
时间复杂度 O ( n ) O(n) O(n)
C代码
using LL long long;class Solution {
public:long long countPairs(int n, vectorvectorint edges) {vectorvectorint 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);functionint(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;};vectorint 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;}
};
