锐客网

  1. 首页 > it技术 > >

[一篇看懂]啥是并查集、咋写并查集（附例题）

java

  • 欢迎评论讨论
1. 并查集 -并查集说到底就是个多叉树
1.1. 并查集应用
  • 找连通分量
  • kruscal最小生成树的存储结构
  • 求最近公共祖先（Least Common Ancestors, LCA）
1.2. 怎么写一个并查集
  • 并查集三大部分
    • 初始化
    • 找根
    • 合并: 其中一个根下放另一个并查集的根
1.2.1. 初始化
- parent数组全置为-1
  • parent中存储的如果是非负数: 存的是父节点的下标
  • parent存的是负数: 其绝对值为该并查集的元素个数
1.2.2. 找根
int find(int x) { while(parent[x]>=0) x=parent[x]; return x; }

1.2.3. 合并
union(parent[],i,j) parent[i]=j;

  • j为i的父节点
2. 例题: 岛屿数量
  • https://leetcode-cn.com/problems/number-of-islands/
【[一篇看懂]啥是并查集、咋写并查集（附例题）】给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
3. 答案(并查集解)
  • 遍历二维网格，将竖直或水平相邻的陆地联结。最终，返回并查集数据结构中相连部分的数量。
  • 更多具体思路看这里：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/[一篇看懂]啥是并查集、咋写并查集（附例题）
    文章图片
3.1. 并查集数据结构
class UF{ int[] parent; int count=0; // 连通分量数 UF(char[][] grid){ if(grid==null||grid.length==0) return; int rowN=grid.length; int colN=grid[0].length; parent=new int[rowN*colN]; for(int i=0; i!=rowN; i++) for(int j=0; j!=colN; j++) if(grid[i][j]=='1') { // 已经自动考虑parent是以0开始的 parent[i*colN+j]=-1; count++; // 连通分量初始化 } } int find(int x) { while(parent[x]>=0) x=parent[x]; return x; } void union(int x,int y) { int rootx=find(x); int rooty=find(y); if(rootx==rooty) return; parent[rootx]=rooty; parent[rooty]--; count--; // 合并一次连通分量少一个 } }

3.2. 答案
class Solution { public int numIslands(char[][] grid) { if(grid==null||grid.length==0) return 0; int rowN=grid.length,colN=grid[0].length; UF uf = new UF(grid); for(int i=0; i!=rowN; i++) for(int j=0; j!=colN; j++) if(grid[i][j]=='1') { grid[i][j]='0'; if(i+1

3.3. 测试
public static void main(String[] args) { char[][] grid= {{'1','1','1','1','0'},{'1','1','0','1','0'}, {'1','1','0','0','0'},{'0','0','0','0','0'}}; int test=1; Solution s = new Solution(); int out = s.numIslands(grid); if(out==test) System.out.println("ok"); else System.out.println("fail:"+out); } }

4. 参考link
  • https://www.cnblogs.com/cyjb/p/UnionFindSets.html

    推荐阅读


    上一篇：shell|shell date 扩展功能（-d参数）

    下一篇：Python 实现循环的最快方式