leetcode算法题547
链接：https://leetcode.cn/problems/number-of-provinces
题目
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解法
使用并查集
public static int findCircleNum(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int length = M.length;
UnionFind unionFind = new UnionFind(length);
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (M[i][j] == 1) {
unionFind.union(i, j);
}
}
}
return unionFind.getSize();
}
public static class UnionFind {
private int[] parents;
private int[] childSizes;
private int size;
public UnionFind(int N) {
parents = new int[N];
childSizes = new int[N];
size = N;
for (int i = 0; i < N; i++) {
// 表示第i个位置的父节点为自己
parents[i] = i;
// 表示第i位置的子节点数
childSizes[i] = 1;
}
}
private int findParent(int index) {
Stack<Integer> stack = new Stack<Integer>();
// 从节点开始一直找到最上的父节点
while (index != parents[index]) {
stack.push(index);
index = parents[index];
}
// 自己不是父节点，需要设置父节点
while (!stack.isEmpty()) {
parents[stack.pop()] = index;
}
return index;
}
public void union(int x, int y) {
int a = findParent(x);
int b = findParent(y);
// 父节点不一样，需要合并
if (a != b) {
// 哪个子节点多，哪个成为父节点
if (childSizes[a] >= childSizes[b]) {
parents[b] = a;
childSizes[a] += childSizes[b];
} else {
parents[a] = b;
childSizes[b] += childSizes[a];
}
size--;
}
}
public int getSize() {
return size;
}
}
