1. 并查集

并查集是树形结构，常常在题目中用来判断两个元素是否属于同一个集合，每个集合都有一个特征性元素称为这个集合的father，如果两个元素的father相同，则说明这两个元素属于同一集合,若这两个元素的father不相同，则说明这两个元素不属于一个集合。并查集就是这样一种支持合并和查询的树形数据结构。

  • 初始化
    把每个点所在集合初始化为其自身。
    通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为。
  • 查找
    查找元素所在的集合，即根节点。
  • 合并
    将两个元素所在的集合合并为一个集合。
    通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

2. 547. 省份数量

2.1. 递归方法

  1.     public int findCircleNum(int[][] isConnected) {
  2.         int n = isConnected.length;
  3.         UnionFind unionFind = new UnionFind(n);
  4.         for (int i = 0; i < isConnected.length; i++) {
  5.             for (int j = i + 1; j < isConnected[i].length; j++) {
  6.                 if (isConnected[i][j] == 1) { // j和i 相互认识
  7.                     unionFind.union(i, j);
  8.                 }
  9.             }
  11.         }
  12.         return unionFind.sets;
  13.     }
  15.     public static class UnionFind {
  16.         static int sets;
  17.         static int[] arr;
  19.         public UnionFind(int n) {
  20.             this.sets = n;
  21.             this.arr = new int[n];
  22.             for (int i = 0; i < arr.length; i++) {
  23.                 arr[i] = i;// 初始化并查集数组 每个节点父元素为自己
  24.             }
  25.         }
  27.         // 找父节点
  28.         public static int find(int a) {
  29.             if (a == arr[a]) {
  30.                 return a;
  31.             }
  32.             arr[a] = find(arr[a]);//路径压缩
  33.             return arr[a];
  34.         }
  36.         //合并节点
  37.         public void union(int i, int j) {
  38.             if(find(i) != find(j)){ //如果他们两的父节点 不是一个
  39.                 arr[find(i)] = find(j); //
  40.                 sets--;
  41.             }
  43.         }
  45.     }

2.2. 数组栈实现

  1.     public int findCircleNum(int[][] isConnected) {
  2.         int n = isConnected.length;
  3.         UnionFind unionFind = new UnionFind(n);
  4.         for (int i = 0; i < isConnected.length; i++) {
  5.             for (int j = i + 1; j < isConnected[i].length; j++) {
  6.                 if (isConnected[i][j] == 1) {
  7.                     unionFind.union(i, j); // 两节点认识 合并节点
  8.                 }
  9.             }
  10.         }
  11.         return unionFind.getSets();
  13.     }
  15.     public static class UnionFind {
  16.         // 并查集数组
  17.         private int[] parent;
  18.         // i所在的集合 大小是多少
  19.         private int[] size;
  20.         // 辅助结构 用于实现栈
  21.         private int[] help;
  22.         // 一共有多少个集合
  23.         private int sets;
  25.         public UnionFind(int n) {
  26.             parent = new int[n];
  27.             size = new int[n];
  28.             help = new int[n];
  29.             sets = n;
  30.             // 初始化并查集数组 每个节点的父节点是自身
  31.             for (int i = 0; i < parent.length; i++) {
  32.                 parent[i] = i;
  33.                 size[i] = 1; // 只有自己一个节点
  34.             }
  35.         }
  37.         // 查找父节点
  38.         public int find(int i) {
  39.             int hi = 0;// 辅助数组下标
  40.             // 找父节点
  41.             while (i != parent[i]) {
  42.                 help[hi++] = i;// 记录路径
  43.                 i = parent[i];
  44.             }
  45.             // 路径压缩
  46.             for (hi--; hi >= 0; hi--) {
  47.                 parent[help[hi]] = i; // 将路径上的节点的父节点 全部标记为最顶的父节点i
  48.             }
  50.             return i; // 返回最顶的父节点
  52.         }
  54.         // 合并节点
  55.         public void union(int i, int j) {
  56.             int f1 = find(i); // 找到这个两节点的父节点
  57.             int f2 = find(j);
  58.             if (f1 != f2) { // 他们两认识 父节点又不相同 进行合并
  59.                 if (size[f1] >= size[f2]) { // 将小size的数组 合并到大size的去
  60.                     size[f1] += size[f2];
  61.                     parent[f2] = f1; // 更新f2的父节点为f1的父节点
  62.                 } else {
  63.                     size[f2] += size[f1];
  64.                     parent[f1] = f2;
  65.                 }
  66.                 sets--;
  67.             }
  68.         }
  70.         public int getSets() {
  71.             return sets;
  72.         }
  74.         public void setSets(int sets) {
  75.             this.sets = sets;
  76.         }
  78.     }

3. 200. 岛屿数量

感染问题，经典写法使用dfs搜索，但可以改为并查集实现。

3.1. 深搜写法

  1.     public int numIslands(char[][] grid) {
  2.         int ans = 0;
  3.         for (int i = 0; i < grid.length; i++) {
  4.             for (int j = 0; j < grid[i].length; j++) {
  5.                 if (grid[i][j] == '1') {
  6.                     ans++;
  7.                     dfs(grid, i, j);
  8.                 }
  9.             }
  10.         }
  11.         return ans;
  12.     }
  14.     private void dfs(char[][] grid, int i, int j) {
  15.         if (i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] != '1') {
  16.             // 越界 或 当前岛屿不是1(陆地)
  17.             return;
  18.         }
  19.         grid[i][j] = 3; //感染更改标记
  20.         dfs(grid, i + 1, j);
  21.         dfs(grid, i - 1, j);
  22.         dfs(grid, i, j + 1);
  23.         dfs(grid, i, j - 1);
  25.     }

3.2. 包装成类存储写法

由于0,0是没有数据，我们先遍历第0行和第0列的岛屿（优化时间），再遍历其他岛屿，每个岛屿只搜索上方和左方岛屿。

这里我们将岛屿为1的位置存储为我们的自定义类，存储的为内存地址防止多个岛屿值相同情况，

  1.     public static int numIslands1(char[][] board) {
  2.         int row = board.length;
  3.         int col = board[0].length;
  4.         Dot[][] dots = new Dot[row][col];
  5.         List<Dot> dotList = new ArrayList<>();
  6.         for (int i = 0; i < row; i++) {
  7.             for (int j = 0; j < col; j++) {
  8.                 if (board[i][j] == '1') {
  9.                     dots[i][j] = new Dot();
  10.                     dotList.add(dots[i][j]);
  11.                 }
  12.             }
  13.         }
  14.         UnionFind1<Dot> uf = new UnionFind1<>(dotList);
  15.         for (int j = 1; j < col; j++) {
  16.             // (0,j)  (0,0)跳过了  (0,1) (0,2) (0,3)
  17.             if (board[0][j - 1] == '1' && board[0][j] == '1') {
  18.                 uf.union(dots[0][j - 1], dots[0][j]);
  19.             }
  20.         }
  21.         for (int i = 1; i < row; i++) {
  22.             if (board[i - 1][0] == '1' && board[i][0] == '1') {
  23.                 uf.union(dots[i - 1][0], dots[i][0]);
  24.             }
  25.         }
  26.         for (int i = 1; i < row; i++) {
  27.             for (int j = 1; j < col; j++) {
  28.                 if (board[i][j] == '1') {
  29.                     if (board[i][j - 1] == '1') {
  30.                         uf.union(dots[i][j - 1], dots[i][j]);
  31.                     }
  32.                     if (board[i - 1][j] == '1') {
  33.                         uf.union(dots[i - 1][j], dots[i][j]);
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.         return uf.sets();
  39.     }
  41.     public static class Dot {
  43.     }
  45.     public static class Node<V> {
  47.         V value;
  49.         public Node(V v) {
  50.             value = v;
  51.         }
  53.     }
  55.     public static class UnionFind1<V> {
  56.         public HashMap<V, Node<V>> nodes;
  57.         public HashMap<Node<V>, Node<V>> parents;
  58.         public HashMap<Node<V>, Integer> sizeMap;
  60.         public UnionFind1(List<V> values) {
  61.             nodes = new HashMap<>();
  62.             parents = new HashMap<>();
  63.             sizeMap = new HashMap<>();
  64.             for (V cur : values) {
  65.                 Node<V> node = new Node<>(cur);
  66.                 nodes.put(cur, node);
  67.                 parents.put(node, node);
  68.                 sizeMap.put(node, 1);
  69.             }
  70.         }
  72.         public Node<V> findFather(Node<V> cur) {
  73.             Stack<Node<V>> path = new Stack<>();
  74.             while (cur != parents.get(cur)) {
  75.                 path.push(cur);
  76.                 cur = parents.get(cur);
  77.             }
  78.             while (!path.isEmpty()) {
  79.                 parents.put(path.pop(), cur);
  80.             }
  81.             return cur;
  82.         }
  84.         public void union(V a, V b) {
  85.             Node<V> aHead = findFather(nodes.get(a));
  86.             Node<V> bHead = findFather(nodes.get(b));
  87.             if (aHead != bHead) {
  88.                 int aSetSize = sizeMap.get(aHead);
  89.                 int bSetSize = sizeMap.get(bHead);
  90.                 Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
  91.                 Node<V> small = big == aHead ? bHead : aHead;
  92.                 parents.put(small, big);
  93.                 sizeMap.put(big, aSetSize + bSetSize);
  94.                 sizeMap.remove(small);
  95.             }
  96.         }
  98.         public int sets() {
  99.             return sizeMap.size();
  100.         }
  102.     }

3.3. 将二维数组转为一维写法

二维转一维：i*列数+j

  1.     public int numIslands(char[][] grid) {
  2.         int row = grid.length; // 行
  3.         int col = grid[0].length; // 列
  4.         UnionFind uf = new UnionFind(grid);
  5.         for (int i = 1; i < col; i++) {
  6.             if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
  7.                 uf.union(0, i - 1, 0, i);
  8.             }
  9.         }
  10.         for (int i = 1; i < row; i++) {
  11.             if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
  12.                 uf.union( i - 1, 0, i,0);
  13.             }
  14.         }
  16.         for (int i = 1; i < row; i++) {
  17.             for (int j = 1; j < col; j++) {
  18.                 if (grid[i][j] == '1') {
  19.                     if (grid[i][j - 1] == '1') {
  20.                         uf.union(i, j - 1, i, j);
  21.                     }
  22.                     if (grid[i - 1][j] == '1') {
  23.                         uf.union(i - 1, j, i, j);
  24.                     }
  25.                 }
  26.             }
  27.         }
  29.         return uf.getSets();
  31.     }
  33.     public static class UnionFind {
  34.         int[] parent; // 并查集数组
  35.         int[] size; // 存储为大小
  36.         int[] help; // 压缩路径辅助数组 用于模拟栈
  37.         int col; // 列
  38.         int sets; // 父节点数量
  40.         // 初始化
  41.         public UnionFind(char[][] grid) {
  42.             col = grid[0].length; // 列
  43.             sets = 0;
  44.             int row = grid.length; // 行
  45.             int len = row * col;// 陆地和水的总数量
  46.             parent = new int[len];
  47.             size = new int[len];
  48.             help = new int[len];
  50.             for (int i = 0; i < row; i++) {
  51.                 for (int j = 0; j < col; j++) {
  52.                     if (grid[i][j] == '1') {
  53.                         int ind = index(i, j);
  54.                         parent[ind] = ind;
  55.                         size[ind] = 1;
  56.                         sets++;
  57.                     }
  58.                 }
  59.             }
  61.         }
  63.         private int index(int i, int j) {
  64.             // 二维转一维：i*列数+j
  65.             return i * col + j;
  66.         }
  68.         private int find(int i) {
  69.             int hi = 0;
  70.             // 找父节点
  71.             while (i != parent[i]) {
  72.                 help[hi++] = i;
  73.                 i = parent[i];
  74.             }
  75.             // 压缩路径
  76.             for (hi--; hi >= 0; hi--) {
  77.                 parent[help[hi]] = i;
  78.             }
  80.             return i;
  81.         }
  83.         private void union(int r1, int c1, int r2, int c2) {
  84.             int a = index(r1, c1);
  85.             int b = index(r2, c2);
  86.             int f1 = find(a);
  87.             int f2 = find(b);
  88.             if (f1 != f2) {
  89.                 if (size[f1] >= size[f2]) {
  90.                     size[f1] += size[f2];
  91.                     parent[f2] = f1;
  92.                 } else {
  93.                     size[f2] += size[f1];
  94.                     parent[f1] = f2;
  95.                 }
  96.                 sets--; // 减少父节点数量
  97.             }
  98.         }
  100.         public int getSets() {
  101.             return sets;
  102.         }
  104.         public void setSets(int sets) {
  105.             this.sets = sets;
  106.         }
  108.     }

4. 305.岛屿数据 II

m行和列的 2d 网格图n最初充满水。我们可以执行addLand操作，将位置 (row, col) 的水变成陆地。给定要操作的位置列表，计算每次addLand操作后的岛数。岛屿四面环水，由相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

例子：

  1. 输入： m = 3，n = 3，位置 = [[0,0]，[0,1]，[1,2]，[2,1]]
  2. 输出： [1,1,2,3]

解释：

最初，二维网格grid充满水。（假设 0 代表水，1 代表土地）。

  1. 0 0 0
  2. 0 0 0
  3. 0 0 0

操作 #1：addLand(0, 0) 将 grid[0][0] 处的水变成陆地。

  1. 1 0 0
  2. 0 0 0 岛屿数 = 1
  3. 0 0 0

操作 #2：addLand(0, 1) 将 grid[0][1] 处的水变成陆地。

  1. 1 1 0
  2. 0 0 0 岛屿数 = 1
  3. 0 0 0

操作 #3：addLand(1, 2) 将 grid[1][2] 处的水变成陆地。

  1. 1 1 0
  2. 0 0 1 岛屿数 = 2
  3. 0 0 0

操作 #4：addLand(2, 1) 将 grid[2][1] 处的水变成陆地。

  1. 1 1 0
  2. 0 0 1 岛屿数 = 3
  3. 0 1 0
  1. public static List<Integer> numIslands21(int m, int n, int[][] positions) {
  2.         UnionFind unionFind = new UnionFind(m, n);
  3.         List<Integer> ans = new ArrayList<>();
  4.         for (int[] i : positions) {
  5.             ans.add(unionFind.connect(i[0], i[1]));
  6.         }
  8.         return ans;
  10.     }
  12.     public static class UnionFind {
  13.         int[] parent;
  14.         int[] help;
  15.         int[] size;
  16.         final int row;
  17.         final int col;
  18.         int sets;
  20.         public UnionFind(int row, int col) {
  21.             this.row = row;
  22.             this.col = col;
  23.             int len = row * col;
  24.             parent = new int[len];
  25.             help = new int[len];
  26.             size = new int[len];
  27.             sets = 0;
  28.         }
  30.         public int index(int r, int c) {
  31.             return r * col + c;
  32.         }
  34.         public int find(int i) {
  35.             int hi = 0;
  36.             while (i != parent[i]) {
  37.                 help[hi++] = i;
  38.                 i = parent[i];
  39.             }
  40.             for (hi--; hi >= 0; hi--) {
  41.                 parent[help[hi]] = i;
  42.             }
  43.             return i;
  44.         }
  46.         public void union(int r1, int c1, int r2, int c2) {
  47.             if (r1 < 0 || r1 == row || c1 < 0 || c1 == col || r2 < 0 || r2 == row || c2 < 0 || c2 == col) {
  48.                 // 边界处理
  49.                 return;
  50.             }
  51.             int a = index(r1, c1);
  52.             int b = index(r2, c2);
  53.             if (size[a] == 0 || size[b] == 0) {
  54.                 // 两节点 有任意一节点未经过 合并无意义
  55.                 return;
  56.             }
  57.             int f1 = find(a);
  58.             int f2 = find(b);
  59.             if (f1 != f2) {
  60.                 if (size[f1] >= size[f2]) {
  61.                     size[f1] += size[f2];
  62.                     parent[f2] = f1;
  63.                 } else {
  64.                     size[f2] += size[f1];
  65.                     parent[f1] = f2;
  66.                 }
  67.                 sets--;
  68.             }
  70.         }
  72.         public int connect(int r, int c) {
  73.             int index = index(r, c);
  74.             // 该节点之前没有经过的
  75.             if (size[index] == 0) {
  76.                 // 初始化
  77.                 parent[index] = index;
  78.                 size[index] = 1;
  79.                 sets++;
  80.                 // 上下左右合并
  81.                 union(r + 1, c, r, c);
  82.                 union(r - 1, c, r, c);
  83.                 union(r, c + 1, r, c);
  84.                 union(r, c - 1, r, c);
  85.             }
  86.             return sets;
  87.         }
  89.     }