【深度优先搜索2】联通块统计（邻接表存储）

图的深度优先遍历

深度优先遍历（DFS）是一种经典的图遍历算法。通过该算法，我们可以遍历一个图的所有节点，并将连通的节点标记为已访问。以下是 DFS 的基本实现：

visited = [False] * (MAX)  # 访问标记数组

# DFS 函数（递归实现）
def dfs(node):
    visited[node] = True  # 标记当前节点为已访问
    for neighbor in adj[node]:  # 遍历该节点的邻居
        if not visited[neighbor]:  # 如果邻居未被访问
            dfs(neighbor)  # 递归访问邻居节点

我们可以通过下面的例子来更好的了解一下深度优先搜索。

对于这个联通块，蓝色节点代表未被访问的节点，黑色代表节点已被访问的节点，黄色边框代表当前节点的邻居节点。

假设我们从节点2开始，我们需要做的就是把这个联通块所有的节点打上一个标记 进入节点2的函数调用栈，对节点2打上标记，然后尝试访问节点2的所有邻居节点，假设这里先访问节点1 标记节点1，然后访问邻居节点，此时，发现节点2已经访问过了，选择跳过节点2，对节点5进行访问(进入函数调用栈)。

那么我们可以看到节点5接下来没有可以访问的节点，那只能把节点5出栈。 现在的节点1跟节点5同理出栈，回到节点2 接下来就是重复以上的操作~，最后会把整个连通块打上标记 我们了解图的深度优先遍历是怎么进行的了 开始尝试这道题目

题解

题面描述

给定一张无向图，图中有 n 个节点和 m 条边。请计算图中的连通块数量。连通块是图的一个最大子图，其中任意两个节点之间都有路径相连。

思路分析

为了计算无向图中的连通块数量，我们可以采用 深度优先搜索（DFS） 算法，按照上面的例子所讲思路的把连通块打标记。以下是详细的思路分析：

1.那么我们第一步首先是根据输入把图构建好~ 参考图的存储

MAX = 1001  # 假设最大节点数为 1000
adj = [[] for _ in range(MAX)]  # 邻接表存储图
visited = [False] * (MAX)  # 访问标记数组

2.接下来，我们从输入读取图的边，并构建邻接表：

for _ in range(m):
    u, v = map(int, input().split())
    if u != v:  # 忽略自环
        adj[u].append(v)
        adj[v].append(u)

3.计算联通块的数量

在构建完图后，我们可以通过遍历每个节点，启动 DFS 来统计图中的连通块数。对于每个未被访问的节点，启动一次 DFS 来遍历它所在的连通块，同时更新连通块计数器。

count = 0  # 连通块计数器

# 遍历所有节点，进行 DFS
for i in range(1, n + 1):
    if not visited[i]:
        dfs(i)  # 启动 DFS
        count += 1  # 每次启动 DFS，发现一个新的连通块

完整代码

MAX = 1001  # 假设最大节点数为 1000
adj = [[] for _ in range(MAX)]  # 邻接表存储图
visited = [False] * (MAX)  # 访问标记数组

# DFS 函数（递归实现）
def dfs(node):
    visited[node] = True  # 标记当前节点为已访问
    for neighbor in adj[node]:  # 遍历该节点的邻居
        if not visited[neighbor]:  # 如果邻居未被访问
            dfs(neighbor)  # 递归访问邻居节点

def main():
    n, m = map(int, input().split())  # 读取节点数和边数

    # 初始化邻接表和访问标记数组
    for i in range(1, n + 1):
        visited[i] = False
        adj[i] = []

    # 读取边并构建邻接表
    for _ in range(m):
        u, v = map(int, input().split())
        if u != v:  # 忽略自环
            adj[u].append(v)
            adj[v].append(u)

    # 统计联通块数量
    count = 0
    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i)  # 启动 DFS
            count += 1  # 每次启动 DFS，发现一个新的连通块

    print(count)

if __name__ == "__main__":
    main()

题目描述

给定一张无向图，图中的每个节点用一个整数编号，且图通过邻接表存储。请你计算该图中有多少个连通块。我们定义一个连通块是一个图的最大子图，在这个子图中任意两个节点都有路径相连。换句话说，连通块是一个连通的无向图的部分，其中任意两个节点通过一系列边相互连接。

输入

第一行包含两个整数 $n$ 和 $m$，表示图中有 $n$ 个节点（编号为 $1, 2, \dots, n$），$m$ 条边。接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示存在一条无向边连接节点 $u$ 和节点 $v$。

输出

输出一个整数，表示图中的连通块数量。

输入样例

5 3
1 2
2 3
4 5

输出样例

2

数据范围

• 图中的节点数 $n$ 满足 $1 \leq n \leq 1000$。
• 图中的边数 $m$ 满足 $0 \leq m \leq \frac{n(n-1)}{2}$。
• 图中每条边连接的两个节点 $u$ 和 $v$ 满足 $1 \leq u, v \leq n$，且 $u \neq v$。
• 图中可能包含自环和多重边，但这些不影响连通块的计算。