LeetCode 1319. 连通网络的操作次数 C#
原题链接
中等
作者:
hpstory
,
2022-08-15 17:08:44
,
所有人可见
,
阅读 123
C# 代码
// 模板题,并查集求连通块数量
public class Solution {
private int[] q;
public int MakeConnected(int n, int[][] connections) {
if (connections.Length < n - 1) return -1;
this.q = new int[n];
int result = 0;
for (int i = 0; i < n; i++) q[i] = i;
foreach (int[] connection in connections){
q[Find(connection[0])] = Find(connection[1]);
}
for (int i = 0; i < n; i++){
if (Find(i) == i) result++;
}
return result - 1;
}
private int Find(int x){
if (q[x] != x) q[x] = Find(q[x]);
return q[x];
}
}