并查集的作用

并查集是一种利用一维数组而构成的模板类，在判断图的连通，岛屿数量等问题有着十分关键的作用，并且并查集的使用和构建也非常简单

并查集的构建

class bincha{
    //数据总数
    int n;
    //记录当前独立的个体数量，每合并一次，setCount--
    int setCount;
    //每个数据的同类代表节点
    int[] parent;
    //每个同类数据集的数量，初始size都是1，x和y合并之后，其中一个数size[x]+=size[y],size[y]=0
    int[] size;
    //初始化并查集
    public bincha(int n){
        this.n = n;
        this.setCount = n;
        for (int i = 0; i < n; i++ ) {
            parent[i] = i;
        }
        Arrays.fill(size, 1);
    }
    
    //找同类代表节点
    public int find(int x){
        //注意，写成parent[x] = find(parent[x])是为了及时更新同类节点，方便更快速查找，其实也可以只写find(parent[x])
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    //合并数据集
    public boolean unite(int x, int y){
        x = find(x);
        y = find(y);
        if (x == y){
            //同类节点，不需要合并
            return false;
        }
        //合并优化操作，我们规定，合并的时候，总是将小数据集合并到大数据集
        if(size[x] < size[y]) {
            int temp = y;
            y = x;
            x = temp;
        }
        //合并
        parent[y] = x;
        size[x] += size[y];
        size[y] = 0;
        setCount--;
    }
    //判断两个数据是否连接
    public boolean connected(int x, int y){
        x = find(x);
        y = find(y);
        return x==y;
    }
}

并查集的应用

1.岛屿问题 给定一个二维数组，0表示海，1表示陆地，求岛屿数量或者最大岛屿大小

我们可以将二维数组表示成一维数组的形式，一维数组的下标即为二维数组的横坐标乘纵向宽度+纵坐标。 初始化并查集，注意，0的地方size也为0,1的地方size为1。其他初始化方法不变。

从左至右，从上至下遍历二维数组，遇到1，就找其是否有正上方及正左方的1，有的话，合并，没有的话就不做操作。

2.图的连通问题 给定一个二维数组，表示边

同样构建一个大小为n的并查集(n为点的个数)，遍历二维数组，unite(i,grid[i]中的每一个数)。

3.二分图问题 给定一个二维数组，表示边

同样构建一个大小为n的并查集(n为点的个数)，遍历二维数组，connected(i,grid[i]中的每一个数)，因为一条边的两个点不能在同一个集，如果connected方法返回true，直接判错。如果没有返回true，再unite(grid[i][0],grid[i]中的每一个数)。因为同一个点的多个邻接点肯定在一个集。