如上一个题解所说,这个是并查集的入门题目,但是貌似没有人给出java的代码,因此这里写一个Java题解,权当抛砖引玉
首先定义并查集的模板
class Union_Find_Set{
ArrayList<Integer> father = new ArrayList<>();
int SIZE = 0;
public Union_Find_Set(int size){
this.SIZE = size;
for(int i = 0; i < size; i++){
father.add(i);
}
}
public int find(int x) {
// 递归版本
if (x == father.get(x)) {
return father.get(x);
}
// 递归寻找父节点
int ans = find(father.get(x));
// 找到结点之后,顺手把路径压缩一下,把根·父节点更新为这条链上所有结点的父节点,
//免得后面还要这样递归来查
father.set(x, ans);
return ans;
}
// 非递归版本用的比较少,所以设置为private
private int Find(int x){
// 非递归版本
while (father.get(x) != x){
// 如果当前结点的父节点不是自己的话,就去查询他的父节点
x = father.get(x);
}
// 当当前节点的父节点就是自己,说明找到了
return x;
}
public void union(int a, int b){
// 把两个不相交的集合合并为同一个集合
// 这里把默认a小于b,这样可以避免形成环,
// 不然可能形成a的父节点是b,b的父节点是a的情况,然后find的时候陷入死循环
// 这里可能还存在没考虑到的情况,请提出,或者等我想清楚了再回来修改,23333
// 但是对于这道题没问题
// 第一次修改时间:2019-05-15
int father_a = find(a);
int father_b = find(b);
father.set(father_b, father_a);
}
public boolean isInSameSet(int a, int b){
return find(a) == find(b);
}
public int NumOfSet(){
// 返回整个集合中现有的不相交的集合个数
int ans = 0;
for(int i =0; i < this.SIZE; i++){
if(father.get(i) == i){
ans++;
}
}
return ans;
}
}
然后是题目的代码:
public class Solution_547 {
private class Union_Find_Set{
ArrayList<Integer> father = new ArrayList<>();
int SIZE = 0;
public Union_Find_Set(int size){
this.SIZE = size;
for(int i = 0; i < size; i++){
father.add(i);
}
}
public int find(int x) {
// 递归版本
if (x == father.get(x)) {
return father.get(x);
}
// 递归寻找父节点
int ans = find(father.get(x));
// 找到结点之后,顺手把路径压缩一下,把根-父节点更新为这条链上所有结点的直接父节点,免得后面还要这样递归来查
father.set(x, ans);
return ans;
}
// 非递归版本用的比较少,所以设置为private
private int Find(int x){
// 非递归版本
while (father.get(x) != x){
// 如果当前结点的父节点不是自己的话,就去查询他的父节点
x = father.get(x);
}
// 当当前节点的父节点就是自己,说明找到了
return x;
}
public void union(int a, int b){
// 把两个不相交的集合合并为同一个集合
int father_a = find(a);
int father_b = find(b);
father.set(father_b, father_a);
}
public boolean isInSameSet(int a, int b){
return find(a) == find(b);
}
public int NumOfSet(){
int ans = 0;
for(int i =0; i < this.SIZE; i++){
if(father.get(i) == i){
ans++;
}
}
return ans;
}
}
public int findCircleNum(int[][] M) {
int N = M.length;
Union_Find_Set set = new Union_Find_Set(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(M[i][j] == 1 && !set.isInSameSet(i,j)){
set.union(i, j);
}
}
}
return set.NumOfSet();
}
}