1319. 连通网络的操作次数(leetcode)
https://leetcode.cn/problems/number-of-operations-to-make-network-connected/
并查集模版题
class Solution {
public int makeConnected(int n, int[][] connections) {
// // 图转树,遍历图,找到多余的边,保证去除多余的边后剩余的还能连通
int res=0; // 能多出的网线
init(n);
for(int i=0;i<connections.length;i++)
{
if(find(connections[i][0]) == find(connections[i][1]) ) res++;
else union(connections[i][0],connections[i][1]);
}
int temp=0;
for(int i=0;i<n;i++)
if(p[i]==i) // 计算连通块数量
temp++;
// 连通n块联通块需要n-1条边,若边的数量>=n-1则满足全联通,操作次数固定为n-1
return res >= temp-1 ? temp-1:-1;
}
int[] p;
void init(int n)
{
p=new int[n+1];
for(int i=0;i<n;i++)p[i]=i;
}
int find(int x)
{
return x==p[x] ? x:(p[x]=find(p[x]));
}
void union(int x,int y)
{
p[find(x)]=find(y);
}
}