框架
照搬的参考3.
class UF {
private int count; //记录连通分量个数
private int[] parent; //存储若干棵树
private int[] size; //记录树的大小
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
//将p和q连通
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
//小树接到大树下面
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
//判断p和q是否互相连通
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
// 处于同一棵树上的节点相互连通
return rootP == rootQ;
}
//返回节点x的根节点
private int find(int x) {
//进行路径压缩
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int count() {
return count;
}
}
547. 省份数量
用没有优化的并查集解决.
class Solution {
int[] parent;
int count;
public int findCircleNum(int[][] isConnected) {
count = isConnected.length;
parent = new int[isConnected.length];
for (int i = 0; i < isConnected.length; i++) parent[i] = i;
for (int i = 0; i < isConnected.length; i++) {
for (int j = 0; j < isConnected.length; j++) {
if (i != j && isConnected[i][j] == 1)
union(i, j);
}
}
return count;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
public int find(int x) {
while (parent[x] != x)
x = parent[x];
return x;
}
}
参考
comments powered by Disqus