当前位置：首页 > news >正文

全国企业信息查询网seo平台是什么意思

news 2025/7/13 12:59:07

全国企业信息查询网,seo平台是什么意思,广东网站建设案例,网络域名ip查询2316. 统计无向图中无法互相到达点对数原题地址： 力扣每日一题：统计无向图中无法互相到达点对数给你一个整数 n ，表示一张无向图中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 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];}
}