并查集练习

• build(n, nums)：一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
• find(i)：查找 i 所在集合的代表元素，代表元素来代表 i 所在集合，往上找的过程
• boolean isSameSet(a,b)：判断 a 和 b 在不在一个集合里
• void union(a,b)：a 所在集合的所有元素与 b 所在集合所有元素合并成一个集合
• 各种操作单次调用的均摊 O(1)

200. 岛屿数量

注意：为确保索引唯一性，index 函数应使用网格列数 m 进行行列转换。

因为列数 m 表示每行中有多少列。如果我们知道每行的列数，那么我们知道需要跳过多少个元素才能从一行移动到下一行。

而行数 n 通常不表示每列中的元素数目（除非是在一个完全对称的网格中，即 n == m）。

class Solution {public static int MAXN = 100001;public static int[] father = new int[MAXN];public int cols;public int sets;public int numIslands(char[][] grid) {// 对网格中的每个1做并查集，对他做一个以为下标int n = grid.length;int m = grid[0].length;build(n, m, grid);// 遍历网格中的每个1for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(grid[i][j]=='1'){// 查看该位置的左和上两个方向是否为1，是就放入一个集合if(i > 0 && grid[i-1][j] == '1'){union(i,j,i-1,j);}if(j > 0 && grid[i][j-1] == '1'){union(i,j,i,j-1);}}}}return sets;}public void build(int n, int m, char[][] grid){cols = m;sets = 0;for(int i = 0; i < n; i++){for(int j = 0, index; j < m; j++){if(grid[i][j]=='1'){index = index(i,j);father[index] = index;sets++;}}}}public int index(int a, int b){return a *cols + b;}public int find(int i){if(i != father[i]){father[i] = find(father[i]);}return father[i];}public void union(int a, int b, int c, int d){int fx = find(index(a,b));int fy = find(index(c,d));if(fx != fy){father[fx] = fy;sets--;}}
}