LeetCode 547. 并查集
原题链接
简单
作者:
JustDoIt11
,
2023-10-12 12:42:49
,
所有人可见
,
阅读 49
class Solution {
int[][] isConnected;
int[] p = new int[300];
int cnt;
public void init() {
for (int i = 0; i < p.length; i ++ ) {
p[i] = i;
}
}
public int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public int findCircleNum(int[][] _isConnected) {
init();
isConnected = _isConnected;
cnt = isConnected.length;
for (int i = 0; i < isConnected.length; i ++ ) {
for (int j = 0; j < isConnected[i].length; j ++ ) {
if (isConnected[i][j] == 1) {
int pi = find(i); int pj = find(j);
if (pi != pj) {
p[pi] = pj;
cnt -- ;
}
}
}
}
return cnt;
}
}