Argost's Home

并查集

 
  • 2023年 05月27日

一些算法举例

并查集&染色问题

岛屿个数&朋友圈（islands&Friends Circles）

给定一个1（陆地）和0（水）组成的二维网络，计算岛屿数量，一个岛被水包围，并且它是通过水平方向或者垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

  • 示例

    a.
输入：
11000
11000
00100
00011
  
输出：
3
  
b
输入：
110
110
001
  
输出：
3
      A B C
      1 1 0
      1 1 0
      0 0 1

  • 解析

    其实岛屿问题和朋友圈问题本质是一样的，朋友圈其实也是孤岛问题。

    第一种方式：染色方式

    ​ a:遍历节点

    ​ if node==1

    ​ count++;//将node和附件陆地的节点->0

    ​ else

    ​ //不管

    并查集方式

    ​ a:初始化-针对所有为1的节点

    ​ b:遍历所有节点-1合并，0不管

    ​ c:遍历parents

  • 代码

    /*
 *给定一个1（陆地）和0（水）组成的二维网络，计算岛屿数量，一个岛被水包围，并且它是通过水平方向或者垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
 */
func numIslands(_ grid: [[Int]]) -> Int {
    var result = -1;
    //不动原数组
    var copyGrid = [[Int]].init(grid)
  
    var count = 0;
      
    for i in 0..<copyGrid.count {
        for j in 0..<copyGrid[i].count {
            if copyGrid[i][j] == 1 {
                //表明有岛或者是认识的朋友
                count += 1
                dfs(&copyGrid, i, j)
            }
        }
    }
      
    result = count
  
    print("numIslands is \(result)")
    return result;
}
  
func dfs(_ grid: inout [[Int]], _ i: Int, _ j: Int) {
    if i < 0 || j < 0 || i >= grid.count || j >= grid[i].count || grid[i][j] == 0 {
        //不管，啥也不做
        return
    }
      
    grid[i][j] = 0
      
    dfs(&grid, i, j - 1)
    dfs(&grid, i, j + 1)
    dfs(&grid, i - 1, j)
    dfs(&grid, i + 1, j)
}
  
  
========================LeetCode: FloodFillandIslands=========================
let islands = [
            [1,1,0,0,0],
            [1,1,0,0,0],
            [0,0,1,0,0],
            [0,0,0,1,1]
        ]
          
let _ = numIslands(islands)
  
======
numIslands is 3

    并查集的方式，需要先建立并查集，这里暂不实现了

搜索