文章目录
- 785. 判断二分图（图 DFS，染色）
- 207. 课程表（拓扑排序，有向无环图）
- 684. 冗余连接（并查集）
- 695. 岛屿的最大面积（DFS）
- 200. 岛屿数量（DFS）
- 463. 岛屿的周长
785. 判断二分图（图 DFS，染色）
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
思路：这个本质上可以理解为染色问题，相邻两个点的染色不一致就是二分图了
class
Solution
(
object
)
:
def
isBipartite
(
self
,
graph
)
:
"""
:type graph: List[List[int]]
:rtype: bool
"""
# 初始化颜色 -1，0 和 1 两种染色
colors
=
[
-
1
]
*
len
(
graph
)
for
i
in
range
(
len
(
graph
)
)
:
# 遍历每一个结点
if
colors
[
i
]
==
-
1
and
not
self
.
dfs
(
i
,
0
,
colors
,
graph
)
:
# 如果都没有染色且dfs返回False
return
False
return
True
def
dfs
(
self
,
cur_node
,
cur_color
,
colors
,
graph
)
:
if
colors
[
cur_node
]
!=
-
1
:
# 如果当前结点已经涂了颜色
return
colors
[
cur_node
]
==
cur_color
#当前结点的颜色和该点应该的颜色相等(承接下面if条件的)
# 给结点涂颜色
colors
[
cur_node
]
=
cur_color
for
next_node
in
graph
[
cur_node
]
:
#遍历相邻的结点，1-cur_color 表示涂相反的颜色
if
not
self
.
dfs
(
next_node
,
1
-
cur_color
,
colors
,
graph
)
:
# 该结点0，那结点就涂1，反之亦然
return
False
return
True
207. 课程表（拓扑排序，有向无环图）
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
-
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。 -
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
思路1：BFS，统计每个结点的入度和邻接表，将所有入度为 0 的结点存在队列中，队列不为空时，一个一个出队列，出队列的结点的所有后继结点入度 -1（相当于删除了该出队列的结点），如果后继结点的入度 -1 后入度为 0（只有出队列的结点为前继结点），则继续添加到队列中！统计所有出队列的结点的数量，如果和原结点相同，则无环！
参考： https://leetcode-cn.com/problems/course-schedule/solution/tuo-bu-pai-xu-by-liweiwei1419/
class
Solution
(
object
)
:
def
canFinish
(
self
,
numCourses
,
prerequisites
)
:
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
# 课程的长度
clen
=
len
(
prerequisites
)
if
clen
==
0
:
# 没有课程，当然可以完成课程的学习
return
True
# 步骤1：统计每个顶点的入度，搭建邻接矩阵
# 入度数组，记录了指向它的结点的个数，一开始全部为 0
in_degrees
=
[
0
for
_
in
range
(
numCourses
)
]
# 邻接表，使用set是为了去重
adj
=
[
set
(
)
for
_
in
range
(
numCourses
)
]
# 这里[set()]*numCourses 这样的话每个set都一样
# [0, 1] 表示 1 在先，0 在后，注意：邻接表存放的是后继 successor 结点的集合
for
second
,
first
in
prerequisites
:
in_degrees
[
second
]
+=
1
# 统计每个点的入度
adj
[
first
]
.
add
(
second
)
# 搭建邻接表
# 步骤2：拓扑排序开始之前，先把所有入度为 0 的结点加入到一个队列中
# 首先遍历一遍，把所有入度为 0 的结点都加入队列
queue
=
[
]
for
i
in
range
(
numCourses
)
:
if
in_degrees
[
i
]
==
0
:
queue
.
append
(
i
)
counter
=
0
while
queue
:
top
=
queue
.
pop
(
0
)
counter
+=
1
# 步骤3：把这个结点的所有后继结点的入度减去 1（删掉这个结点），如果发现入度为 0（后继结点只有这一个结点的前继） ，就马上添加到队列中
for
successor
in
adj
[
top
]
:
in_degrees
[
successor
]
-=
1
if
in_degrees
[
successor
]
==
0
:
queue
.
append
(
successor
)
return
counter
==
numCourses
思路二：DFS
bryant
684. 冗余连接（并查集）
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
-
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
-
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
思路：
大致可以这么理解，每个结点表示每位侠客，初始化的时候，每个侠客都是单独的门派，边表示两人狭路相逢要打架了，首先自报家门，
- 如果来自不同门派，就一决雌雄（谁赢由你代码决定），然后把决斗的两者的门派归并成胜利一方的门派
- 如果来自同一门派，表示形成回路了，返回这两位大侠
（参考 并查集详解（超级简单有趣~~就学会了））
也可以这么理解：
有点像贪吃蛇，点就是每条蛇，边表示两蛇之间的游动遭遇了，遍历每条边，就表示遍历每次遭遇战，
- 如果两条蛇不是一个队伍的，就一方吃掉另一方（壮大自己）
- 如果两条蛇是一个队伍的，自己吃自己……死了
class
UnionFind
:
def
__init__
(
self
,
n
)
:
# n 为边的数量
self
.
ids
=
[
i
for
i
in
range
(
n
+
1
)
]
# 创建了边+1个门派，初始化门派名为结点（大侠）名
def
find
(
self
,
p
)
:
# 找门派
return
self
.
ids
[
p
]
def
connect
(
self
,
u
,
v
)
:
# 是否来自同一门派
return
self
.
find
(
u
)
==
self
.
find
(
v
)
def
union
(
self
,
u
,
v
)
:
# 把大侠 u 所在的门派合并到大侠 v 门派
u_id
=
self
.
find
(
u
)
# 报门派
v_id
=
self
.
find
(
v
)
# 报门派
if
u_id
==
v_id
:
# 同一个门派，就不用合并了
return
for
i
in
range
(
len
(
self
.
ids
)
)
:
#遍历每位大侠
if
self
.
ids
[
i
]
==
u_id
:
self
.
ids
[
i
]
=
v_id
# 把 u 门派的大侠，合并到 v 的门派
class
Solution
(
object
)
:
def
findRedundantConnection
(
self
,
edges
)
:
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
uf
=
UnionFind
(
len
(
edges
)
)
# 初始化门派
for
u
,
v
in
edges
:
if
uf
.
connect
(
u
,
v
)
:
# 如果两位大侠来自同一门派
return
u
,
v
uf
.
union
(
u
,
v
)
# 把 u 所在门派的大侠们合并到 v 所在的门派
return
695. 岛屿的最大面积（DFS）
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
思路：遍历 grid，对每个岛屿（=1的点）进行一次 dfs，遍历过的岛屿变成陆地，输出最大的 dfs 结果即可！
class
Solution
(
object
)
:
def
maxAreaOfIsland
(
self
,
grid
)
:
"""
:type grid: List[List[int]]
:rtype: int
"""
r
,
c
=
len
(
grid
)
,
len
(
grid
[
0
]
)
def
dfs
(
i
,
j
)
:
# 计算每一个点的四个方向的深度遍历
if
0
<=
i
<
r
and
0
<=
j
<
c
and
grid
[
i
]
[
j
]
:
#只遍历大陆
grid
[
i
]
[
j
]
=
0
# 遍历过的点不参与面积的计算（变成海洋）
return
1
+
dfs
(
i
-
1
,
j
)
+
dfs
(
i
+
1
,
j
)
+
dfs
(
i
,
j
-
1
)
+
dfs
(
i
,
j
+
1
)
else
:
return
0
# 越界的话返回 0
result
=
0
for
i
in
range
(
r
)
:
for
j
in
range
(
c
)
:
if
grid
[
i
]
[
j
]
:
# 只遍历有岛屿的点
result
=
max
(
result
,
dfs
(
i
,
j
)
)
#输出最大的结果
return
result
200. 岛屿数量（DFS）
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
-
示例 1:
输入:
11110
11010
11000
00000
输出: 1 -
示例 2:
输入:
11000
11000
00100
00011
输出: 3
思路：斜着的不算，4 邻域不是 8 邻域，同
695. 岛屿的最大面积
一样，要注意的是数据类型，这里是 str，695 是 int，我们在695的基础上，把每次的 dfs 结果存起来，计算长度即可！
class
Solution
(
object
)
:
def
numIslands
(
self
,
grid
)
:
"""
:type grid: List[List[str]]
:rtype: int
"""
if
grid
==
[
]
:
# 极端情况
return
0
row
,
col
=
len
(
grid
)
,
len
(
grid
[
0
]
)
def
dfs
(
i
,
j
)
:
# dfs 遍历每个岛屿的大小
if
0
<=
i
<
row
and
0
<=
j
<
col
and
grid
[
i
]
[
j
]
==
"1"
:
grid
[
i
]
[
j
]
=
"0"
# 计算过的岛就让他变成海洋（这句最重要了），访问过的就不再访问了
return
1
+
dfs
(
i
-
1
,
j
)
+
dfs
(
i
+
1
,
j
)
+
dfs
(
i
,
j
-
1
)
+
dfs
(
i
,
j
+
1
)
else
:
return
0
list1
=
[
]
for
r
in
range
(
row
)
:
for
c
in
range
(
col
)
:
if
grid
[
r
]
[
c
]
==
"1"
:
# 遍历整个地图，只在有岛的地方用 dfs
list1
.
append
(
dfs
(
r
,
c
)
)
# 把结果存在列表中
return
len
(
list1
)
# 返回列表的长度
463. 岛屿的周长
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
-
示例 :
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
输出: 16
解释: 它的周长是下面图片中的 16 个黄色的边：
思路：比较直接（笨）的方法是，统计每个有岛的地方，遍历四领域，有岛屿的话，边长被覆盖 -1
class
Solution
(
object
)
:
def
islandPerimeter
(
self
,
grid
)
:
"""
:type grid: List[List[int]]
:rtype: int
"""
r
,
c
=
len
(
grid
)
,
len
(
grid
[
0
]
)
total_num
=
0
for
i
in
range
(
r
)
:
for
j
in
range
(
c
)
:
if
grid
[
i
]
[
j
]
==
1
:
num
=
0
if
0
<=
i
-
1
<
r
and
0
<=
j
<
c
and
grid
[
i
-
1
]
[
j
]
==
1
:
num
+=
1
if
0
<=
i
+
1
<
r
and
0
<=
j
<
c
and
grid
[
i
+
1
]
[
j
]
==
1
:
num
+=
1
if
0
<=
i
<
r
and
0
<=
j
-
1
<
c
and
grid
[
i
]
[
j
-
1
]
==
1
:
num
+=
1
if
0
<=
i
<
r
and
0
<=
j
+
1
<
c
and
grid
[
i
]
[
j
+
1
]
==
1
:
num
+=
1
total_num
+=
(
4
-
num
)
return
total_num
