图片无版权网站,胶州网站开发,网页设计公司杭州,做车展招商的网站2316. 统计无向图中无法互相到达点对数
中等
给你一个整数 n #xff0c;表示一张 无向图 中有 n 个节点#xff0c;编号为 0 到 n - 1 。同时给你一个二维整数数组 edges #xff0c;其中 edges[i] [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
请你返回 无法互相…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 1050 edges.length 2 * 105edges[i].length 20 ai, bi nai ! bi不会有重复边。
DFS
class Solution {// 统计联通分量 个数 和 大小// 然后递推求出点对个数// 例如 4 1 2// 4 * 1 5 * 2public long countPairs(int n, int[][] edges) {ListInteger[] 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];ListInteger 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, ListInteger[] 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]));}MapInteger, 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];}
}
