1.连通分量（并查集）
2.合并集合（并查集）
3.连通块中点的数量（并查集）
4.合根植物（并查集）
5.蓝桥幼儿园（并查集）
6.七段码（DFS+并查集）
7.连通块的3种求法（DFS，BFS，并查集）
8.小猪存钱罐（并查集）
9.小朋友崇拜圈

1.连通分量（并查集）

//普通DFS写法,并查集写法在下面
import java.util.*;

public class Main{
    static boolean[][] vis;
    static int[] x= {-1,1,0,0};
    static int[] y= {0,0,-1,1};
    static int n=0,m=0;
    static int num=1;
    public static int dfs(char[][] arr,int i,int j) { 
        for(int a=0;a<4;a++) {
            int newx=i+x[a];
            int newy=j+y[a];
            if(newx>=0&&newx<n&&newy>=0&&newy<m&&arr[newx][newy]=='.'&&vis[newx][newy]==false) {
                vis[newx][newy]=true;
                num++;
                dfs(arr,newx,newy);
            }
        }
        return num;
    }

    public static void init(boolean[][] vis) {
        num=1;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                vis[i][j]=false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        vis=new boolean[n][m];
        char[][] arr=new char[n][m];
        for(int i=0;i<n;i++) {
            arr[i]=input.next().toCharArray();
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j]=='*') {
                    int t=dfs(arr,i,j);
                    arr[i][j]=(char) (t%10+'0');
                    init(vis);
                }
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }

    }
}

//用并查集写了一下,但是由于JAVA读入数据的原因还是超时,听别人说要用什么快读,目前还不会,学习一下并查集的写法就行了
import java.util.*;

public class Main{
    static int n,m; //n行m列
    static char[][] arr; //读入地图
    static int[] p; //存i的父节点
    static int[] s; //s为该节点所在区域的空格的数量
    static int[] dx= {-1,1,0,0};
    static int[] dy= {0,0,-1,1};

    //二维坐标转一维坐标
    public static int get(int x,int y) {
        return x*m+y;
    }

    //找x的根节点
    public static int find(int x) {
        if(p[x]!=x) {
            p[x]=find(p[x]);
        }
        return p[x];
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        int N=1010,M=N*N;
        arr=new char[N][N];
        p=new int[M];
        s=new int[M];
        for(int i=0;i<n;i++) {
            arr[i]=input.next().toCharArray();
        }
        //初始化
        for(int i=0;i<n*m;i++) {
            p[i]=i;
            s[i]=1;
        }
        //维护并查集
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j]=='.') { //如果该区域为空格的话
                    for(int k=0;k<4;k++) { //循环遍历上下左右
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if(x>=0&&x<n&&y>=0&&y<m&&arr[x][y]=='.') { //如果坐标合法的话
                            //将二维坐标转化为一维坐标
                            int a=get(i,j);
                            int b=get(x,y);
                            //找到a,b的根节点
                            a=find(a);
                            b=find(b);
                            //如果a,b的根节点不同,那么就将其合为一体
                            if(a!=b) {
                                s[b]+=s[a];//将a,b两区域合并(合并到b中)
                                p[a]=b;//将a的父节点设为b,此时a,b的父节点均为b
                            }
                        }
                    }
                }
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                //如果为空格,则直接输出
                if(arr[i][j]=='.') System.out.print(arr[i][j]);
                else {
                    //fathers用来存上下左右4个方向的节点的根节点
                    Set<Integer> fathers=new HashSet<Integer>();
                    //循环遍历上下左右4个方向
                    for(int k=0;k<4;k++) {
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if(x>=0&&x<n&&y>=0&&y<m&&arr[x][y]=='.') {
                            int a=get(x,y);//二维坐标一维化
                            //将当前节点的根节点存入(去重)
                            fathers.add(find(a));
                        }
                    }
                    //初始值为1,因为还要加上自身
                    int sum=1;
                    if(fathers.size()>0) {
                        for (Integer integer : fathers) {
                            sum+=s[integer];
                        }
                    }
                    System.out.print(sum%10);
                }
            }
            System.out.println();
        }
    }       
}

2.合并集合（并查集）

//并查集(基础)
import java.util.Scanner;

public class Main {
    //p[x]表示x的父节点
    static int[] p;

    //返回x的祖宗节点+路径压缩
    public static int find(int x) {
        if(p[x]!=x) {//此时说明x不是祖宗节点
            //使其父节点等于其祖宗节点(相当于状态压缩)
             p[x]=find(p[x]);
        }
        //此时返回的x的父节点其实是x的祖宗节点
        return p[x];
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        p=new int[n+5];
        //初始时每个点都是一个单独的集合，此时每个点的祖宗节点都它自己
        for(int i=1;i<=n;i++) {
            p[i]=i;
        }
        while(m--!=0) {
            char[] op=input.next().toCharArray();
            int a,b;
            a=input.nextInt();
            b=input.nextInt();
            if(op[0]=='M') {
                p[find(a)]=find(b);
            }else {
                if(find(a)==find(b)) {
                    System.out.println("Yes");
                }else {
                    System.out.println("No");
                }
            }
        }
    }   
}

3.连通块中点的数量（并查集）

//并查集
import java.util.Scanner;

public class Main {
    //p[x]表示x的父节点
    static int[] p;
    //p[x]表示x所在连通块(集合)中点的数量
    static int[] size;

    //返回x的祖宗节点+路径压缩
    public static int find(int x) {
        if(p[x]!=x) {//此时说明x不是祖宗节点
            //使其父节点等于其祖宗节点(相当于状态压缩)
             p[x]=find(p[x]);
        }
        //此时返回的x的父节点其实是x的祖宗节点
        return p[x];
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        p=new int[n+5];
        size=new int[n+5];
        //初始时每个点都是一个单独的集合，此时每个点的祖宗节点都它自己
        for(int i=1;i<=n;i++) {
            p[i]=i;
            //每个集合中初始点的数量为1
            size[i]=1;
        }
        while(m--!=0) {
            String op=input.next();
            int a,b;
            if(op.equals("C")) {
                a=input.nextInt();
                b=input.nextInt();
                //如果a和b在同一个集合里,那么直接不用算
                if(find(a)==find(b)) continue;
                //只保留根节点里面的size是有意义的 
                //因为是将a并入到b里面,所以b里面的节点的数数量+=a里面节点的数量
                size[find(b)]+=size[find(a)];
                //将a并入到b里面,构成一个新集合
                p[find(a)]=find(b);
            }else if(op.equals("Q1")){
                a=input.nextInt();
                b=input.nextInt();
                if(find(a)==find(b)) {
                    System.out.println("Yes");
                }else {
                    System.out.println("No");
                }
            }else {
                a=input.nextInt();
                System.out.println(size[find(a)]);
            }
        }
    }       
}

4.合根植物（并查集）

//并查集
import java.util.Scanner;

public class Main {
    static int n,m;
    static int k;
    static int[] p; //存i的父节点

    //返回x节点的根节点
    public static int find(int x) {
        if(p[x]!=x) {
            p[x]=find(p[x]);
        }
        return p[x];
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        p=new int[n*m+5];
        //初始化
        for(int i=1;i<=n*m;i++) {
            p[i]=i;//最初父节点都为自身
        }
        k=input.nextInt();
        while(k-->0) {
            int a=input.nextInt();
            int b=input.nextInt();
            //将位置a和位置b的植物合并
            p[find(a)]=find(b);
        }
        //找出合根植物的数量
        int cnt=0;
        for(int i=1;i<=n*m;i++) {
            //其实就是这个节点是这个集合的代表元素(根节点)
            if(p[i]==i) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

5.蓝桥幼儿园（并查集）

//并查集
import java.util.Scanner;

public class Main {
    static int n,m;
    static int[] p;

    public static int find(int x) {
        if(p[x]!=x) {
            p[x]=find(p[x]);
        }
        return p[x];
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        p=new int[n+5];
        //初始化,每个节点的父节点都是自身(每个点都是一个单独的集合)
        for(int i=1;i<=n;i++) {
            p[i]=i;
        }
        while(m-->0) {
            int t=input.nextInt();
            int a=input.nextInt();
            int b=input.nextInt();
            if(t==1) { //连接a和b(将a和b合并成一个集合)
                p[find(a)]=find(b);
            }
            if(t==2) { //判断a和b是否属于一个集合
                if(find(a)==find(b)) {//如果a的根节点等于b的根节点的话,那么a,b属于同一个集合
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
            }
        }
    }
}

6.七段码（DFS+并查集）

实现思路：DFS+并查集
对于每一根二极管都可以选或者不选,用递归来枚举发光二极管的所有情况.
在递归结束的位置用并查集去判断所选择的二极管是不是连通的(在同一个集合中)

//DFS+并查集
//结果为80
public class Main {
    static int[][] arr=new int[10][10];
    static boolean[] use=new boolean[10];//表示当前位置的二极管是否是亮着的
    static int[] p=new int[10];
    static int ans=0;

    public static void init() {
        //a b c d e f g
        //1 2 3 4 5 6 7
        //用二维数组来记录哪2条边是相连的;
        arr[1][2]=arr[1][6]=1;
        arr[2][7]=arr[2][3]=1;
        arr[3][4]=arr[3][7]=1;
        arr[4][5]=1;
        arr[6][7]=1;
        arr[5][6]=arr[5][7]=1;
    }

    //返回x的根节点
    public static int find(int x) {
        if(p[x]!=x) {
            p[x]=find(p[x]);
        }
        return p[x];
    }

    public static void dfs(int cur) {
        //递归尾部
        if(cur==7) {
            //初始化
            for(int i=1;i<=7;i++) {
                p[i]=i;
            }
            //二重循环遍历
            for(int i=1;i<=7;i++) {
                for(int j=i+1;j<=7;j++) {
                    //如果满足条件,将这2个二极管合并
                    if(arr[i][j]==1&&use[i]&&use[j]) {
                        p[find(i)]=find(j);
                    }
                }
            }
            //判断所有的二极管是不是在同一个集合中
            int cnt=0;
            for(int i=1;i<=7;i++) {
                //如果当前二极管是亮的且当前节点的父节点是等于它自身的(当前节点为此集合的根节点)
                if(use[i]&&find(i)==i) {
                    cnt++;
                }
            }
            //如果cnt==1表明只有一个根节点,即当前二极管是连通的
            if(cnt==1)  ans++;
            return ;
        }
        //下面是2条分支分别为:将当前灯亮起,将当前灯熄灭
        use[cur+1]=true;
        dfs(cur+1);
        use[cur+1]=false;
        dfs(cur+1);
    }

    public static void main(String[] args) {
        init();
        dfs(0);
        System.out.println(ans);
    }
}

7.连通块的3种求法（DFS，BFS，并查集）

实现思路：先要维护并查集,我们先遍历一下地图，找到值为W的位置，然后看其上下左右4个方向，如果某个方向没有越界
且值也为W的话，那么说明这2个位置是连通的，此时我们将其合并成一个集合。一直找下去，直至地图遍历完后，我们已经
将所有相连的位置都合并成集合了，最后再重新遍历一下地图，如果某个点的值为W且这个点的根节点为它自己的话（即这
个点为该集合的根节点，也可以说成这个点是这个集合的代表元素），那么连通块数量加1，遍历完以后输出连通块总数即
可

import java.util.Scanner;

public class Main {
    static int n,m;
    static char[][] arr;
    static int[] p;
    static int[] dx= {-1,1,0,0};
    static int[] dy= {0,0,-1,1};

    //二维坐标转一维
    public static int get(int x,int y) {
        return m*x+y;
    }

    //返回x的根节点
    public static int find(int x) {
        if(p[x]!=x) {
            p[x]=find(p[x]);
        }
        return p[x];
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        arr=new char[n][m];
        p=new int[n*m+5];
        for(int i=0;i<n;i++) {
            arr[i]=input.next().toCharArray();
        }
        //初始化
        for(int i=0;i<n*m;i++) {
            p[i]=i;
        }
        //维护并查集
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j]=='W') {
                    for(int k=0;k<4;k++) {//遍历4个方向
                        int x=i+dx[k];
                        int y=j+dy[k];
                        //下一步满足条件
                        if(x>=0&&x<n&&y>=0&&y<m&&arr[x][y]=='W') {
                            int a=get(i,j);//a是前一步位置的坐标(已一维化)
                            int b=get(x,y);//b是下一步位置的坐标(已一维化)
                            a=find(a);//取得a,b的根节点
                            b=find(b);
                            if(a!=b) {
                            //如果a,b的根节点不同的话(不在同一个集合),那么我们将a,b合并(使其成为一个集合)
                                p[a]=b;
                            }
                        }
                    }
                }
            }
        }
        int cnt=0;
        //将地图遍历一遍
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j]=='W') {
                    int a=get(i,j);
                    //如果该点的根节点等于自己的话,即自己为这个集合的根节点(代表元素),那么cnt++
                    if(find(a)==a) {
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

8.小猪存钱罐（并查集）

import java.util.*;

public class Main{
    static int n;
    static int[] p;

    public static int find(int x) { 
        if(p[x]!=x) {
            p[x]=find(p[x]);
        }
        return p[x];
    }


    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        p=new int[n+5];
        for(int i=1;i<=n;i++) {
            p[i]=i;
        }
        for(int i=1;i<=n;i++) {
            int a=input.nextInt();
            if(a!=i)
            p[find(a)]=find(i);
        }
        int cnt=0;
        for(int i=1;i<=n;i++) {
            if(i==find(i)) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

9.小朋友崇拜圈

import java.util.Scanner;

public class Main {
    static int[] arr;
    static boolean[] vis;
    static int max=1;
    public static void dfs(int x,int cur,int t) {
        //如果这个点为true则表示之前已经走过，现在又到了这里，表示已经形成了一个环
        if(vis[x]) {
            //如果这个环的起始和末位都是同一个人的话，那么这个环是正确的
            if(arr[x]==arr[t]) {
                if(cur>max) {
                    max=cur;
                }
            }
            return ;
        }
        vis[x]=true;
        //这里是arr[x]，表示第x个小朋友崇拜的人是第几个
        dfs(arr[x],cur+1,t);
        vis[x]=false;
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        arr=new int[n+5];
        vis=new boolean[n+5];
        for(int i=1;i<=n;i++) {
            arr[i]=input.nextInt();
        }
        for(int i=1;i<=n;i++) {//从第一个小朋友开始
            int t=i;//将当前是第几个小朋友标记出来
            dfs(i,0,t);
        }
        System.out.println(max);
    }
}