并查集

模板

问题描述

给定若干组随机的两两有关系的元素之后。输入一组元素，要求判断相互之间是否有关系（关系具有传递性）。

思路

将每一个关系网总结为一个关系集合，用集合中的某一个元素代表根节点，建立一个树状结构，判断二元素有无关系只需观察二元素根节点是否相同。

如果需要添加一组“元素关系”与另一组“元素关系”即进行UNION操作，则只要对二根节点进行操作，判断哪一个根节点作为新的父节点即可，此时有两种优化方式：一是通过size优化，根节点少的作为根节点多的的子节点，二是通过rank优化，树高度较低的作为高度较高的子节点，二者产生的均为相对最优解。

代码模板

普通方式

class DSU{//Disjoint Set Union模板
        int[] parent;
        public DSU(int N)//初始化，将所有节点父节点设为自己
        {
            parent = new int[N];
            for(int i =0;i<N;i++)
            {parent[i]=i;}
        }
        public int find(int x)//找根节点
        {
            if (parent[x]!=x)
            {
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        public void union(int x,int y)//并集操作，将二者置为有关系
        {
            parent[find(x)]= find(y);
        }
    }

优化1（size）

class DSU{//Disjoint Set Union模板
        int[] parent;
          int[] size;
        public DSU(int N)//初始化，将所有节点父节点设为自己
        {
            parent = new int[N];
            size = new int[N];
            for(int i =0;i<N;i++)
            {parent[i]=i;}
          Arrays.fill(size,1);//初始化，置1
        }
        public int find(int x)//找根节点
        {
            if (parent[x]!=x)
            {
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        public void union(int x,int y)//并集操作，将二者置为有关系
        {        int rootx = find(x);
                 int rooty = find(y);
                 if(rootx==rooty) return;
             if(size[rootx]<=size[rooty])
          {
            parent[rootx] = rooty;
            size[rooty]+=size[rootx];//判断谁节点更多，由节点更多的作为父节点
          }
         else if(size[rootx]> size[rooty])
         {
           parent[rooty] = rootx;
            size[rootx]+=size[rooty];//判断谁节点更多，由节点更多的作为父节点
         }
        }
    }

优化2（rank）

class DSU{//Disjoint Set Union模板
        int[] parent;
          int[] rank;
        public DSU(int N)//初始化，将所有节点父节点设为自己
        {
            parent = new int[N];
            size = new int[N];
            for(int i =0;i<N;i++)
            {parent[i]=i;}
          Arrays.fill(rank,1);//初始化，置1
        }
        public int find(int x)//找根节点
        {
            if (parent[x]!=x)
            {
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        public void union(int x,int y)//并集操作，将二者置为有关系
        {        int rootx = find(x);
                 int rooty = find(y);
                 if(rootx==rooty) return;
             if(rank[rootx]<rank[rooty])
          {
            parent[rootx] = rooty;
          }
         else if(rank[rootx]> rank[rooty])
         {
           parent[rooty] = rootx;
         }
         else
         {
            parent[rooty] = rootx;
           rank++;//仅深度相等时需要维护
         }
        }
    }

例题：[305. 岛屿数量 II]

题目描述：

给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。

可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。

返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。

岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）

• 操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。此时存在 1 个岛屿。
• 操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。此时存在 1 个岛屿。
• 操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。此时存在 2 个岛屿。
• 操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。此时存在 3 个岛屿。

输入：m = 1, n = 1, positions = [[0,0]]
输出：[1]

提示：

1 <= m, n, positions.length <= 104
1 <= m * n <= 104
positions[i].length == 2
0 <= ri < m
0 <= ci < n

import java.util.ArrayList;
import java.util.List;
class Solution {
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};//位置坐标变换
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
      DSU dsu = new DSU(m*n);
      boolean[][] island = new boolean[m][n];
      List<Integer> res = new ArrayList<>();
      int count = 0;
      for(int []cur:positions)//对于position中每一个操作位置进行操作， 产生岛屿
      {
        if(island[cur[0]][cur[1]])
        {
            res.add(count);//加入了一个岛屿
            continue;
        }
        island[cur[0]][cur[1]] = true;//将岛屿操作中所经历的点置为true
        count++;//岛屿增加
        for(int[] dir:dirs)//判断是否相连
      {
          int x =cur[0]+dir[0];//同行点的横坐标
          int y =cur[1]+dir[1];//同列点的纵坐标
          if(x <0||x==m||y<0||y==n||!island[x][y])//出边界或者该地未被变为岛屿
          {
              continue;
          }
          int component1 = dsu.find(cur[0]*n+cur[1]);//找到位置1:position中的操作位置
          int component2 = dsu.find(x*n+y);//找到位置2:循环中有x与y的位置
          if(component1!=component2)
          {
              dsu.union(component1,component2);//设定1与2有关系，使二者根节点相同（将1与2合并为同一岛屿）
              count--;//岛屿数减1
          }
      }
      res.add(count);
      }return res;
    }
    class DSU{//Disjoint Set Union模板
        int[] parent;
        public DSU(int N)//初始化，将所有节点父节点设为自己
        {
            parent = new int[N];
            for(int i =0;i<N;i++)
            {parent[i]=i;}
        }
        public int find(int x)//找根节点
        {
            if (parent[x]!=x)
            {
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        public void union(int x,int y)
        {
            parent[find(x)]= find(y);
        }//岛屿长度较小，暂时没有优化
    }
}