import collections

q = collections.deque([start])

while q:

node_u = q.popleft()

q.append(node_v)

- [323. 无向图中连通分量的数目 - 力扣（LeetCode）](https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/)

给定 `n` 个节点（编号从 `0` 到 `n - 1`）的图的无向边列表 `edges`，其中 `edges[i] = [u, v]` 表示节点 `u` 和节点 `v` 之间有一条无向边。

要求：计算该无向图中连通分量的数量。

先来看一下图论中相关的名次解释。

- 连通图：在无向图中，如果可以从顶点 $v_i$ 到达 $v_j$，则称 $v_i$ 和 $v_j$ 连通。如果图中任意两个顶点之间都连通，则称该图为连通图。

- 无向图的连通分量：如果该图为连通图，则连通分量为本身；否则将无向图中的极大连通子图称为连通分量，每个连通分量都是一个连通图。

- 无向图的连通分量个数：无向图的极大连通子图的个数。

接下来我们来解决这道题。

由于题目给定的是无向边列表。我们先将其转变为邻接表的形式。然后使用广度优先搜索计算联通分量的个数。具体做法如下：

- 使用变量 `count` 记录连通分量个数。使用集合变量 `visited` 记录访问过的节点，使用邻接表 `graph` 记录图结构。

- 从 `0` 开始，依次遍历 `n` 个节点。

- 如果第 `i` 个节点未访问过：

- 将其添加到 `visited` 中。

- 并且连通分量个数累加，即 `count += 1`。

- 定义一个队列 `q`，将第 `i` 个节点加入到队列中。

- 从队列中取出第一个节点，遍历与其链接的节点，并将未遍历过的节点加入到队列 `q` 和 `visited` 中。

- 直到队列为空，则继续向后遍历。

- 最后输出连通分量数目 `count`。

import collections

class Solution:

def countComponents(self, n: int, edges: List[List[int]]) -> int:

count = 0

visited = set()

graph = [[] for _ in range(n)]

for x, y in edges:

graph[x].append(y)

graph[y].append(x)

for i in range(n):

if i not in visited:

visited.add(i)

count += 1

q = collections.deque([i])

while q:

node_u = q.popleft()

for node_v in graph[node_u]:

if node_v not in visited:

visited.add(node_v)

q.append(node_v)

return count

示例 ：


图中最大的岛屿面积为 6。

使用广度优先搜索方法。具体做法如下：

1. 使用 `ans` 记录最大岛屿面积。

2. 遍历二维数组的每一个元素，对于每个值为 `1` 的元素：

1. 将该元素置为 `0`。并使用队列 `q` 存储该节点位置。使用 `temp_ans` 记录当前岛屿面积。

2. 然后从队列 `q` 中取出第一个节点位置 `(i, j)`。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为 `0`（避免重复搜索）。并将其加入到队列中。并累加当前岛屿面积，即 `temp_ans += 1`。

3. 不断重复上一步骤，直到队列 `q` 为空。

4. 更新当前最大岛屿面积，即 `ans = max(ans, temp_ans)`。

import collections

class Solution:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

rows, cols = len(grid), len(grid[0])

ans = 0

for i in range(rows):

for j in range(cols):

if grid[i][j] == 1:

grid[i][j] = 0

temp_ans = 1

q = collections.deque([(i, j)])

while q:

i, j = q.popleft()

for direct in directs:

new_i = i + direct[0]

new_j = j + direct[1]

if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols or grid[new_i][new_j] == 0:

continue

grid[new_i][new_j] = 0

q.append((new_i, new_j))

temp_ans += 1

ans = max(ans, temp_ans)

return ans