Graph 图

BFS/DFS 例题

Connected Components 连通分量

https://cses.fi/problemset/task/1666

一个连通分量是无向图中一个最大的连通节点集合。换句话说，两个节点位于同一个连通分量中，当且仅当它们可以通过图中的边相互到达。

在上述重点问题中，目标是添加尽可能少的边，使得整个图形成一个单一的连通分量。

Solution - Building Roads

请注意，每条边会将连通分量的数量减少零个或一个。因此，您必须至少添加 $C-1$ 条边，其中 $C$ 是输入图中的连通分量数量。

为了计算 $C$ ，可以遍历每个节点。如果该节点尚未被访问，则使用 DFS 或 BFS 访问该节点及其所在连通分量的所有其他节点。然后 $C$ 等于我们执行访问操作的次数。

有许多有效的方法可以选择 $C−1$ 条新的道路来建设。一种方法是为每个 $C$ 连通分量选择一个代表节点，并将它们连接成一条线。

BFS

import sys

sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

adj = [[] for _ in range(n)]
visited = [False] * n

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

c = 0

connect = []

def dfs(node):
    visited[node] = True
    for v in adj[node]:
        if not visited[v]:
            dfs(v)
    
for i in range(n):
    if not visited[i]:
        c += 1
        connect.append(i)
        dfs(i)

print(c-1)
for i in range(c-1):
    print(connect[i]+1, connect[i+1]+1)

DFS

from collections import deque

n, m = map(int, input().split())

adj = [[] for _ in range(n)]
visited = [False] * n

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

c = 0

connect = []
    
for i in range(n):
    if not visited[i]:
        c += 1
        connect.append(i)
        q = deque([i])
        while q:
            node = q.popleft()
            visited[node] = True
            for v in adj[node]:
                if not visited[v]:
                    q.append(v)

print(c-1)
for i in range(c-1):
    print(connect[i]+1, connect[i+1]+1)

Graph Two-Coloring 图的二色染色

https://cses.fi/problemset/task/1668

图的二色化指的是为图中的每个节点分配一个布尔值，该值由边的配置决定。最常见的二色图例子是二分图，在这种图中，每条边连接两个颜色不同的节点。

在上述重点问题中，目标是将图中的每个节点（朋友）分配到两种颜色（队伍）之一，满足边（友谊）连接两个颜色不同的节点的约束条件。换句话说，我们需要检查输入是否为二分图，如果是，则输出一种有效的着色方案。

---

大编号节点建图

问题背景

当节点编号 $u, v$ 的范围很大（如 $1 \leq u, v \leq 10^9$），但实际边的数量 $m$ 较小时，无法直接用邻接表 adj = [[] for _ in range(n)] 建图，因为会消耗过多内存。

解决方案：使用字典 + 离散化

方法一：直接使用 defaultdict（推荐）

from collections import defaultdict

adj = defaultdict(list)
nodes = set()

# 读取边
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    nodes.add(u)
    nodes.add(v)

# 遍历
for node in nodes:
    for nei in adj[node]:
        print(f"{node} -> {nei}")

优点： - 无需离散化，直接使用原始编号 - 代码简洁，适合竞赛编程

方法二：离散化（坐标压缩）

from collections import defaultdict

# 第一步：收集所有节点编号
nodes = set()
for _ in range(m):
    u, v = map(int, input().split())
    nodes.add(u)
    nodes.add(v)

# 第二步：建立映射（原始编号 → 连续编号）
node_list = sorted(nodes)  # 排序后映射
node_id = {node: i for i, node in enumerate(node_list)}
n = len(node_list)

# 第三步：使用连续编号建图
adj = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[node_id[u]].append(node_id[v])

优点： - 可以使用数组，访问速度更快 - 适合需要频繁随机访问的场景

复杂度分析

方法	时间	空间
defaultdict	$O(m)$	$O(m)$
离散化	$O(m \log m)$（排序）	$O(m)$

适用场景

• 节点编号大、边数少：优先使用 defaultdict
• 需要频繁随机访问：考虑离散化
• 需要保留节点编号信息：使用 defaultdict 更方便