并查集概念

并查集（Union-Find）是一种树型的数据结构，用于处理一些不交集的合并及查询问题。其主要应用是判断两个元素是否在同一个集合中，以及合并两个集合。

并查集的常见操作

构建并查集

public class Main12 
{
    public static void main(String[] args) {
        int[] father=new int[11];
        for(int i=1;i<=10;i++)
        {
            father[i]=i;
        }
    }
}

这样构建的数组的每一个元素都是一个单独的集合没有任何交集。
就像这样

合并并查集和查找

public class Main12
{
    static int[] father=new int[11];
    public static void main(String[] args) {

        for(int i=1;i<=10;i++)
        {
            father[i]=i;
        }
         father[find(1)]=find(2);
        father[find(3)]=find(2);
        father[find(2)]=find(4);
    }
    public static int find(int x)
    {
        while(x!=father[x])
        {
            x=father[x];
        }
        return father[x];
    }
}

father数组里面存是当前元素的父节点，看个图片就理解了。
find函数是查找元素的根节点
以这个并查集为例子：
father[find(1)]=find(2);
father[find(3)]=find(2);
father[find(2)]=find(4);

我们先将集合1合并到集合2，再将集合3合并到集合2，最后将集合2合并到集合4。
集合的合并：例如合并集合1和集合2 father[find(1)]=find(2);就是将2的根节点赋值给1的根节点就可以了

看这幅图片就可以很好理解father数组里面存是当前元素的父节点
在并查集里面只有根节点的x==[father[x],通过这个特点我们可以查找集合元素的根节点，当两个元素根节点相同时则属于同一个集合，否则就不在同一集合。

关于find函数

public static int find(int x)
    {
        while(x!=father[x])
        {
            x=father[x];
        }
        return father[x];
    }

我们以这种写法找根节点的时候如果我们查找n-1元素的根节点的时候需要将整棵树遍历一遍效率比较低。

find的第二种写法

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

这种写法有个名字叫路径压缩，效率高，但是有个缺点就是会破坏树的结构。
举个例子：

看第一幅图我们可以知道1的父节点应该是2，但是如果使用路径压缩，1的父节点被修改为了1。意味着树的结构变为了这样

大家根据具体的需要选择合适的find方法。
并查集模板练习

import java.util.Scanner;
public class Main
{
    static int N,M;
    static int[] arr;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
         N=scanner.nextInt();
         M=scanner.nextInt();
         arr=new int[N+10];
        for(int i=1;i<=N;i++)
        {
            arr[i]=i;
        }
        while((M--)>0)
        {
            int z=scanner.nextInt();
            int x=scanner.nextInt();
            int y=scanner.nextInt();
            if(z==1)
            {
               arr[find(x)]=find(y);
            }
            else
            {
                if(find(x)==find(y))
                {
                    System.out.println("Y");
                }
                else
                {
                    System.out.println("N");
                }
            }
        }
    }
    static int find(int x) {
        if (x != arr[x]) 
        arr[x] = find(arr[x]);
        return arr[x];
    }
}

村村通题目练习

import java.util.Scanner;
public class Main
{
    static int N,M;
    static int[] arr;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
         N=scanner.nextInt();
         M=scanner.nextInt();
         arr=new int[N+10];
        for(int i=1;i<=N;i++)
        {
            arr[i]=i;
        }
        while((M--)>0)
        {
            int z=scanner.nextInt();
            int x=scanner.nextInt();
            int y=scanner.nextInt();
            if(z==1)
            {
               arr[find(x)]=find(y);
            }
            else
            {
                if(find(x)==find(y))
                {
                    System.out.println("Y");
                }
                else
                {
                    System.out.println("N");
                }
            }
        }
    }
    static int find(int x) {
        if (x != arr[x]) 
        arr[x] = find(arr[x]);
        return arr[x];
    }
}

完。