Java并查集的模板

//并查集模板
class DisJoint{
    private int[] father;
 
    public DisJoint(int N) {
        father = new int[N];
        for (int i = 0; i < N; ++i){
            father[i] = i;
        }
    }
 
    public int find(int n) {
        return n == father[n] ? n : (father[n] = find(father[n]));
    }
 
    public void join (int n, int m) {
        n = find(n);
        m = find(m);
        if (n == m) return;
        father[m] = n;
    }
 
    public boolean isSame(int n, int m){
        n = find(n);
        m = find(m);
        return n == m;
    }
 
}

并查集相关题目：107. 寻找存在的路径

文章链接：代码随想录

题解如下：

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int M=sc.nextInt();
int N=sc.nextInt();
Bjc bcj=new Bjc(M+1);
for(int i=0;i<N;i++){
bcj.join(sc.nextInt(),sc.nextInt());
}

if(bcj.isSame(sc.nextInt(),sc.nextInt())){
System.out.println("1");
}else{
System.out.println("0");
}

}
}







class Bcj{
private int[] father;
public Bjc(int N){
father=new int[N];
for(int i=0;i<N;++i){
father[i]=i;
}
}

public int find(int n){

return father[n]==n?n:(father[n]=find(father[n]));
}

public void join(int n,int m){
n=find(n);
m=find(m);
if(n==m) return;

father[m]=n;
}

public boolean isSame(int n,int m){
n=find(n);
m=find(m);

return n==m;
}
}