做百度网站排,网站设计实施,首都在线官网,wordpress开源程序建站教程统计无向图中无法互相到达点对数【LC2316】 给你一个整数 n #xff0c;表示一张 无向图 中有 n 个节点#xff0c;编号为 0 到 n - 1 。同时给你一个二维整数数组 edges #xff0c;其中 edges[i] [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。 请你返回 无法互相到达…统计无向图中无法互相到达点对数【LC2316】 给你一个整数 n 表示一张 无向图 中有 n 个节点编号为 0 到 n - 1 。同时给你一个二维整数数组 edges 其中 edges[i] [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。 请你返回 无法互相到达 的不同 点对数目 。 思路 **并查集查找连通性**记录每个点的父节点父节点相同的节点可以相互到达与父节点不同的节点不可以互相到达计算数量父节点为 i i i的节点数量为 a a a那么这个节点与 n − a n-a n−a个节点不相邻统计数量统计结果由于重复计算最终结果需要除以2 实现 class Solution {public long countPairs(int n, int[][] edges) {// 并查集记录每个点的父节点父节点相同的节点可以相互到达与父节点不同的节点不可以互相到达// 计算数量父节点为i的节点数量为a那么这个节点与n-a个节点不相邻统计数量// 统计结果由于重复计算最终结果需要除以2UnionFind union new UnionFind(n);for (int[] edge : edges){union.union(edge[0], edge[1]);}long res 0L;for (int i 0; i n; i){res n - union.getSize(i);}return res / 2;}
}
// 并查集类
class UnionFind {private int[] p;// 父节点private int[] size;// 每个节点的子节点个数包括自身// 初始化public UnionFind(int n) {p new int[n];size new int[n];for (int i 0; i n; i) {p[i] i;size[i] 1;}}// 找到节点x的根public int find(int x) {if (p[x] ! x) {p[x] find(p[x]);}return p[x];}// 在并查集中加入a-b的根public void union(int a, int b) {int pa find(a), pb find(b);if (pa ! pb) {if (size[pa] size[pb]) {p[pb] pa;size[pa] size[pb];} else {p[pa] pb;size[pb] size[pa];}}}public int getSize(int a){int father find(a);return size[father];}}复杂度分析 时间复杂度 O ( n α ( m ) ∗ m ) O(n\alpha (m)*m) O(nα(m)∗m) n n n为图中顶点的数目 m m m为图中边的数目。其中 α \alpha α为阿克曼函数的反函数其增长极其缓慢也就是说其单次操作的平均运行时间可以认为是一个很小的常数。空间复杂度 O ( n ) O(n) O(n)空间复杂度主要取决于并查集并查集需要 O ( n ) O(n) O(n)的空间因此总的空间复杂度为 O ( n ) O(n) O(n)。
