贵州省建设项目备案查询网站,企业微网站建设方案,免费职业技能培训网,央视新闻2316. 统计无向图中无法互相到达点对数 原题地址#xff1a; 力扣每日一题#xff1a;统计无向图中无法互相到达点对数 给你一个整数 n #xff0c;表示一张 无向图 中有 n 个节点#xff0c;编号为 0 到 n - 1 。同时给你一个二维整数数组 edges #xff0c;其中 edges[i…2316. 统计无向图中无法互相到达点对数 原题地址 力扣每日一题统计无向图中无法互相到达点对数 给你一个整数 n 表示一张 无向图 中有 n 个节点编号为 0 到 n - 1 。同时给你一个二维整数数组 edges 其中 edges[i] [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。
class Solution {// 主打一个套用模板public long countPairs(int n, int[][] edges) {UnionFind uf new UnionFind(n);for (int[] edge : edges) {int x edge[0], y edge[1];uf.union(x, y);}long res 0;for (int i 0; i n; i) {res n - uf.getSize(uf.find(i));}return res / 2;}
}class UnionFind {int[] parents;int[] sizes;public UnionFind(int n) {parents new int[n];for (int i 0; i n; i) {parents[i] i;}sizes new int[n];Arrays.fill(sizes, 1);}public int find(int x) {if (parents[x] x) {return x;} else {parents[x] find(parents[x]);return parents[x];}}public void union(int x, int y) {int rx find(x), ry find(y);if (rx ! ry) {if (sizes[rx] sizes[ry]) {parents[ry] rx;sizes[rx] sizes[ry];} else {parents[rx] ry;sizes[ry] sizes[rx];}}}public int getSize(int x) {return sizes[x];}
}如果对您有帮助请点赞关注支持我谢谢❤ 如有错误或者不足之处敬请指正❤
