统计无向图中无法互相到达点对数【LC2316】
给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。
思路
- **并查集查找连通性：**记录每个点的父节点，父节点相同的节点可以相互到达；与父节点不同的节点，不可以互相到达
- 计算数量，父节点为i的节点数量为a，那么这个节点与n − a个节点不相邻，统计数量
- 统计结果，由于重复计算，最终结果需要除以2
实现
class Solution { public long countPairs(int n, int[][] edges) { // 并查集记录每个点的父节点，父节点相同的节点可以相互到达；与父节点不同的节点，不可以互相到达 // 计算数量，父节点为i的节点数量为a，那么这个节点与n-a个节点不相邻，统计数量 // 统计结果，由于重复计算，最终结果需要除以2 UnionFind 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 ) ，n为图中顶点的数目，m为图中边的数目。其中 α为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。
空间复杂度：O ( n ) ，空间复杂度主要取决于并查集，并查集需要 O ( n )的空间，因此总的空间复杂度为O ( n )
