本文主要是介绍2316. 统计无向图中无法互相到达点对数（leetcode）并查集-------------------Java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2316. 统计无向图中无法互相到达点对数（leetcode）并查集-------------------Java实现
题目表述
给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条无向边。
请你返回 无法互相到达 的不同 点对数目
样例
条件
1 <= n <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不会有重复边。
思路
使用并查集，并通过一个size数组记录并查集长度。
注意点
ac代码
Java:
class Solution {public int find(int n,int[] parent){if(parent[n] == n)return n;parent[n] = find(parent[n],parent);return parent[n];}public void union(int number1,int number2,int[] parent,int[] size){int num1 = find(number1,parent);int num2 = find(number2,parent);if(parent[num1]!=parent[num2]){if(size[num1]>=size[num2]){size[num1] += size[num2];parent[num2] = parent[num1];}else{size[num2] += size[num1];parent[num1] = parent[num2];}}return;}public long countPairs(int n, int[][] edges) {int[] parent = new int[n];int[] size = new int[n];long result = 0;for(int i = 0;i<n;i++)parent[i] = i;Arrays.fill(size,1);for(int[] now:edges)union(now[0],now[1],parent,size);for(int i=0;i<n;i++)result+=(n-size[find(i,parent)]);return result/2;}
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这篇关于2316. 统计无向图中无法互相到达点对数（leetcode）并查集-------------------Java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
