并查集--算法题

妖狐艹你老母 2022-01-12 02:07 200阅读 0赞

## leetcode-200 islands ##

### 题意： ###

给出一个二维数组，只包含 1/0 。1表示陆地，0表示水，求岛屿个数。例：

input：

1 1 0 0 0  
    1 1 0 0 0  
    0 0 1 0 0  
    0 0 0 1 1 
    复制代码

output：

3

### 思路 ###

*  染色法

1.  遍历数组
2.  如果为1，则找到相邻的所有为1的节点，赋值为0，同时count++

2可以用DFS和BFS实现。

> 以下代码会对更改源数组，推荐用visited\[\]。

DFS：每个节点都判断附近有没为1的节点，伪代码如下：

function DFS(x, y) if (int[x][y] := 1){
                int[x][y] := 0
                DFS(x, y+1)
                DFS(x, y-1)
                DFS(x+1, y)
                DFS(x-1, y)
            }
    复制代码

BFS：将所有附近为1的节点都放到queue中，再逐个清理

function BFS(x, y) q.offer(x, y) while (!q.isEmpty){
                (i, j) := q.poll()
                int(i, j) := 0
                if int[i+1][j] := 1 q.offer(i+1, j)
                if int[i-1][j] := 1 q.offer(i-1, j)
                if int[i][j+1] := 1 q.offer(i, j+1)
                if int[i][j-1] := 1 q.offer(i, j-1)
            }
    复制代码

*  并查集

1.  初始化“1”的节点的root为自己
2.  遍历所有节点，相邻合并（只做统计这里可以）
3.  遍历parent，获取详情

## leetcode-547 Friend Circle ##

### 题意 ###

给定一个二维矩阵（权图），1表示认识，0表示不认识，求有多少朋友圈。例：

A B C  
    A  1 1 0  
    B  1 1 0  
    C  0 0 1  
    复制代码

### 思路 ###

这题和leetcode-200其实是一样的，如果有连续相连的“1”，说明这些人互相认识，也就是一个朋友圈，求朋友圈个数也是求有多少个岛屿；也是典型的图的边的矩阵表示方式。

leetcode-200、547直接用并查集方法即可，详见[并查集-理论][-]

--------------------

欢迎关注微信公众号，提供思想和技术类原创文章。微信搜索**小兵张健**或扫描以下二维码。

转载于:https://juejin.im/post/5cedf29ff265da1bbb03bcbb

[-]: https://link.juejin.im?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2FxbWhD9Fczeog_YjJvddrVA

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集算法

文章目录 1. 原理介绍 2. 并查集的应用 3. find()函数的定义与实现 4. 并查集的join函数

以你之姓@/ 2024年03月22日 15:46/ 0 赞/ 55 阅读

相关算法14.并查集

算法|14.图相关算法 1.并查集（map版） package greedy; import java.util.HashMap;

朴灿烈づ我的快乐病毒、/ 2024年03月16日 10:42/ 0 赞/ 48 阅读

相关算法设计——并查集

【蓝桥杯】历届试题合根植物问题描述　　w星球的一个种植园，被分成 m \ n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。　　这

拼搏现实的明天。/ 2023年10月05日 17:32/ 0 赞/ 3 阅读

相关 Java算法——并查集

功能并查集是管理多个集合的算法，其功能包括集合的合并、集合内或集合间的查询。背景在中国古代，人们都比较重视血缘传承，几乎每家都至少会有一个男孩，后人总会牢记

川长思鸟来/ 2023年01月11日 09:07/ 0 赞/ 161 阅读

相关算法笔记【2】并查集

算法笔记【2】并查集并查集简介并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

一时失言乱红尘/ 2023年01月09日 12:58/ 0 赞/ 150 阅读

相关天梯题集——家庭房产（并查集）

家庭房产 ![t1][] ![t2][] -------------------- 解题步骤 ①、并查集将每个家庭都看成一个集合，再统计每个家庭的人数

迈不过友情╰/ 2022年12月23日 07:10/ 0 赞/ 120 阅读

相关【经典算法】:并查集详解

并查集最经典的问题就是找朋友的圈子，见小米的一道面试题，不得不说这些题都是比较简单的。并查集的经典思路就是用pre数组记录掌门人，然后不断的找最大的掌门人，并且同

Bertha 。/ 2022年07月21日 01:55/ 0 赞/ 190 阅读

相关并查集算法理解

并查集算法理解并查集主要就是解决判断两个点两个物体是否有关系，如在最小生成树kr

清疚/ 2022年05月17日 07:42/ 0 赞/ 174 阅读

相关并查集--算法题

leetcode-200 islands 题意：给出一个二维数组，只包含 1/0 。1表示陆地，0表示水，求岛屿个数。例： input： 1 1 0

妖狐艹你老母/ 2022年01月12日 02:07/ 0 赞/ 201 阅读

相关算法：并查集

算法：并查集快速掌握理解算法　　在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合

ゝ一纸荒年。/ 2021年09月30日 11:30/ 0 赞/ 393 阅读