LC-2316. 统计无向图中无法互相到达点对数（DFS、并查集）

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

中等

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 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 <= 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 不会有重复边。

DFS

class Solution {// 统计联通分量 个数 和 大小// 然后递推，求出点对个数// 例如 4 1 2// 4 * 1 + 5 * 2public long countPairs(int n, int[][] edges) {List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for(int[] e : edges){int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}boolean[] vis = new boolean[n];List<Integer> list = new ArrayList<>();for(int i = 0; i < n; i++){if(!vis[i]){int cnt = dfs(i, -1, g, vis);list.add(cnt);}}long res = 0l, sum = 0l;for(Integer e : list){res += e * sum;sum += e;}return res;}private int dfs(int x, int fa, List<Integer>[] g, boolean[] vis){int res = 1;vis[x] = true;for(int y : g[x]){if(y != fa && !vis[y])res += dfs(y, x, g, vis);}return res;}
}

并查集

统计连通块大小可以用并查集做

class Solution {// 统计联通分量 个数 和 大小public long countPairs(int n, int[][] edges) {UF uf = new UF(n);for(int[] e : edges){uf.union(Math.max(e[0], e[1]), Math.min(e[0], e[1]));}Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < n; i++){map.merge(uf.find(i), 1, Integer::sum);}long res = 0l, sum = 0l;for(int x : map.keySet()){res += (long)map.get(x) * sum;sum += map.get(x);}return res;}
}/* ------------ 并查集模版 ------------ */
class UF {int[] parent; // par数组用来存储根节点，par[x]=y表示x的根节点为yint[] size; // size[i]表示以i为根的联通块大小int count; // count表示连通块个数，每次调用union时count-1public UF(int n) {this.count = n;parent = new int[n];size = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}public void union(int x, int y) {int rootx = find(x);int rooty = find(y);if (rootx == rooty) return;else//不是同一个根，即不在同一个集合，就合并parent[rootx] = rooty;size[rooty] += size[rootx];count--;}public int find(int x) {// 路径压缩if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}
}