门户网站开发案例/百度应用商店app下载

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;
}
}