图的存储

本文的目标是 系统性地剖析竞赛中常用的图存储方法，深入比较它们的优劣与适用场景，有效帮助选手们提升实战能力与理论认知。我们将从基础概念入手，逐步深入到各种存储方式的实现细节、时空效率分析、竞赛技巧以及避坑指南，最终让你在面对图论问题时，能够自信且明智地选择并实现最高效的图存储方案。

1. 引言：为何要精通图的存储？

想象一下，你要绘制一张城市的交通地图。你可以选择画一张包含所有街道的详尽地图，也可以只在每个路口标注与之直接相连的其他路口及其距离。这两种方式对应着不同的信息组织形式，适用于不同的查询需求。

在算法竞赛中，图（Graph）是模拟现实世界中各种连接关系（如社交网络、交通路线、依赖关系、状态转移等）的强大数学模型。几乎所有的图算法，无论是基础的 BFS、DFS，还是复杂的 Dijkstra、Floyd、最小生成树、网络流等，其运行效率和内存消耗都严重依赖于你如何有效地存储图的结构信息。

一个 节点的稀疏图，如果用邻接矩阵存储，可能瞬间 MLE；一个需要频繁查询两点是否直接相连的问题，如果用邻接表，效率可能不如邻接矩阵。因此，根据题目特点（点数、边数、图的稠密程度、后续算法需求）选择最优的存储方式，是解决图论问题的第一步，也是至关重要的一步。精通图的存储，能让你在竞赛中避免不必要的性能瓶颈，为后续的算法实现铺平道路。

2. 图论基础回顾（精简版）

在深入存储方法之前，我们快速回顾几个核心概念，确保大家的理解一致。

什么是图？

一个图 由两个集合组成：顶点（Vertex）集合 和边（Edge）集合 。记作 。

• 顶点 (Vertex / Node): 图中的基本单元，通常用数字或字母表示。顶点数常用 或 表示。
• 边 (Edge): 连接两个顶点的线段。边数常用 或 表示。
  • 无向边 (Undirected Edge): 边 表示 和 之间的连接是双向的。
  • 有向边 (Directed Edge / Arc): 边 表示从 出发到 的单向连接。 称为尾（tail）， 称为头（head）。
  • 带权边 (Weighted Edge): 每条边关联一个数值（权重），表示通过这条边的代价、距离或容量等。
  • 无权边 (Unweighted Edge): 所有边的权重视为相同（通常为 1）。

基本术语

• 邻接 (Adjacent): 如果存在边 或 ，则称 和 邻接。
• 度 (Degree):
  • 无向图中，顶点 的度是指与 相关联的边的数量。
  • 有向图中，顶点 的 出度 (Out-degree) 是从 出发的边的数量，入度 (In-degree) 是指向 的边的数量。
• 路径 (Path): 从顶点 到顶点 的一个顶点序列 ，其中 , ，且对于所有 ， 或 都是图中的边。
• 环 (Cycle): 一条起点和终点相同的路径（且至少包含一条边）。
• 稠密图 (Dense Graph): 边数 接近 的图 ()。
• 稀疏图 (Sparse Graph): 边数 远小于 的图（例如 或 ）。竞赛中遇到的图大多是稀疏图。

3. 方法一：邻接矩阵 (Adjacency Matrix)

邻接矩阵是最直观的图存储方式。

核心思想

使用一个二维数组 g[N][N] 来表示图。

• 对于 无权图：g[u][v] = 1 表示顶点 和 之间存在边，g[u][v] = 0 表示不存在。
• 对于 带权图：g[u][v] = w 表示顶点 和 之间存在权重为 的边。如果边不存在，通常用一个特殊值表示，如 0（如果边权保证为正），或者一个 无穷大 值 INF（更通用）。
• 对于 无向图，矩阵是对称的，即 g[u][v] = g[v][u]。
• 对于 有向图，g[u][v] 表示从 到 的边，g[v][u] 表示从 到 的边，两者可能不同。

实现方式与代码示例

题意概括: 读取 个点 条边的带权有向图信息，并存储。然后查询若干次，判断两点间是否有直接边，若有则输出权重。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 505; // 邻接矩阵适用于点数较小的图
const int INF = 0x3f3f3f3f; // 定义无穷大 (对于int权重)
// 如果权重是 long long, INF 应设为类似 1e18
// const ll INF = 1e18;

int g[N][N]; // 邻接矩阵存储
int n, m;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    // 初始化邻接矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) g[i][j] = 0; // 通常自己到自己的距离为0
            else g[i][j] = INF; // 初始时假设点之间不连通
        }
    }

    // 读入边信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 对于有向图
        g[u][v] = min(g[u][v], w); // 处理重边，保留权值最小的边
        // 如果是无向图，需要同时设置 g[v][u]
        // g[v][u] = min(g[v][u], w);
    }

    // 查询示例: 查询从点 a 到点 b 是否有直接边及其权重
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (g[a][b] == INF) {
            // cout << "No direct edge\n";
        } else {
            // cout << "Edge weight: " << g[a][b] << "\n";
        }
    }

    return 0;
}

代码解释:

• INF 的选择：0x3f3f3f3f 是一个常用的 int 型无穷大值，它的好处是 INF + INF 不会溢出 int（只要加数不是特别多），并且它的两倍、加上一个不太大的数等通常还在 int 范围内。对于 long long，使用 1e18 或 LLONG_MAX / 2。
• 初始化：对角线设为 0，其余设为 INF。
• 处理重边：如果输入允许重边，g[u][v] = min(g[u][v], w) 可以确保只存储权重最小的那条边（这在某些算法如 Floyd 中是需要的）。如果题目保证无重边，或要求存储所有边（邻接矩阵做不到），则直接赋值 g[u][v] = w。

时空复杂度分析

• 空间复杂度： 。这是邻接矩阵最大的缺点，它与边数 无关，只取决于顶点数 。当 达到 或 时， 的空间通常是不可接受的（大约需要 400MB 到 40GB 内存）。
• 时间复杂度：
  • 初始化： 。
  • 添加边： 。
  • 查询边 是否存在/获取权重： 。这是邻接矩阵的主要优点。
  • 遍历顶点 的所有邻居： 。需要扫描一行 g[u][...]。
  • 计算顶点 的出度： 。
  • 计算顶点 的入度： （需要扫描一列 g[...][u]）。

优缺点与适用场景

优点：

• 实现简单直观。
• 查询两点间是否存在边以及获取边权非常快 ()。
• 对于 稠密图 ()，空间效率尚可，且 的边查询可能带来优势。

缺点：

• 空间复杂度太高 ()，不适用于 较大的图（竞赛中通常 就需要谨慎）。
• 对于 稀疏图 ()，空间浪费极大。
• 遍历一个点的所有邻居需要 时间，效率低下。很多图算法（如 BFS, DFS, Dijkstra）都需要高效遍历邻居。

适用场景：

• 顶点数 很小（例如 ）。
• 图是稠密的。
• 算法需要频繁查询任意两点间是否直接相连（例如 Floyd-Warshall 算法）。

4. 方法二：邻接表 (Adjacency List) - vector 实现

邻接表是竞赛中最常用、最灵活的图存储方式，尤其适用于稀疏图。

核心思想

为图中的 每个顶点 维护一个 列表，存储所有 从 出发 的边的信息。

具体来说，使用一个数组（或 vector） adj，其中 adj[u] 是一个动态数组（如 std::vector），存储所有以 为起点的边。

• 对于 无权图：adj[u] 存储的是所有与 邻接的顶点 。
• 对于 带权图：adj[u] 存储的是 pair<int, int> 或自定义结构体，每个元素包含 {邻接点 v, 边权 w}。

实现方式与代码示例（竞赛主流）

题意概括: 读取 个点 条边的带权有向图信息，并使用 vector 实现的邻接表存储。然后演示如何遍历一个点的所有出边。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5; // 适用于点数较大的图

// adj[u] 存储所有从 u 出发的边
// 每条边用 pair 表示: {邻接点 v, 边权 w}
vector<pair<int, int>> adj[N];
int n, m;

// 如果是无权图，可以简化为 vector<int> adj[N];

void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
    // 如果是无权图: adj[u].push_back(v);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    // 读入边信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w); // 添加有向边 u -> v

        // 如果是无向图，需要添加反向边
        // add_edge(v, u, w);
    }

    // 示例: 遍历顶点 u 的所有出边 (邻居)
    int u_to_traverse = 1; // 假设遍历顶点 1 的邻居
    // cout << "Edges starting from node " << u_to_traverse << ":\n";
    for (auto& edge : adj[u_to_traverse]) {
        int v = edge.first;  // 邻接点
        int w = edge.second; // 边权
        // 使用 C++17 结构化绑定可以更简洁:
        // for (auto& [v, w] : adj[u_to_traverse]) { ... }
        // cout << "  -> Node " << v << " (Weight " << w << ")\n";
    }

    return 0;
}

代码解释:

• vector<pair<int, int>> adj[N]; 定义了一个数组，数组的每个元素是一个 vector，这个 vector 存储 pair<int, int>。adj[i] 就是顶点 的邻接表。
• add_edge(u, v, w) 函数封装了添加边的操作。
• 遍历邻居：使用基于范围的 for 循环 (for (auto& edge : adj[u])) 是最简洁高效的方式。auto& 避免了不必要的拷贝。

时空复杂度分析

• 空间复杂度： 。
  • 需要 个 vector 对象（或指针/头结点）。
  • 总共存储 条边的信息（对于有向图）或 条边的信息（对于无向图，因为每条无向边存了两次）。
  • 因此，空间复杂度与点数和边数之和成线性关系，非常适合稀疏图。
• 时间复杂度：
  • 初始化： （创建 个空的 vector）。
  • 添加边 ： 平均 。vector::push_back 在摊还意义下是 。
  • 查询边 是否存在/获取权重： ，其中 是顶点 的出度。需要遍历 adj[u]。如果 adj[u] 保持有序，可以用二分查找做到 ，但通常不值得这么做。
  • 遍历顶点 的所有邻居： 。效率很高，与实际出边数量成正比。
  • 计算顶点 的出度： ，即 adj[u].size()。
  • 计算顶点 的入度： 需要遍历所有边，或者在建图时额外维护一个入度数组，复杂度 或 （遍历建图）。如果需要频繁查询入度，建议单独存储。

优缺点与适用场景

优点：

• 空间效率高，尤其适用于稀疏图 ()。
• 遍历一个点的所有邻居非常高效 (）。
• 添加边操作快（摊还 ）。
• 使用 C++ STL vector，实现方便灵活，不易出错。
• 易于存储边的额外信息（使用 pair 或 struct）。

缺点：

• 查询特定边 是否存在相对较慢 (）。

适用场景：

• 绝大多数 算法竞赛中的图论问题，特别是 稀疏图。
• 算法需要高效遍历节点的邻居（如 BFS, DFS, Dijkstra, Prim, Kruskal 的部分实现等）。
• 点数 较大（例如 ）。

处理重边与自环

• 重边： vector 邻接表会存储所有添加的边，包括重边。如果算法要求处理重边（例如，在最短路中只考虑权重最小的边），通常是在算法执行过程中处理（如 Dijkstra 的松弛操作会自动选择更优的），而不是在存储时去重。如果确实需要在存储时去重或合并，会增加建图的复杂度。
• 自环： 自环 也会被正常存储在 adj[u] 中。大多数图算法都能正确处理自环（或者自环不影响结果）。

5. 方法三：链式前向星 (Forward Star)

链式前向星是一种用 纯数组 模拟邻接表的方式，常用于对性能有极致要求或内存限制非常严格的场景，或者在一些不支持动态内存分配的环境（虽然在 ICPC 中不常见）。它在 C 语言风格的代码和一些经典算法实现（如图匹配、网络流）中较为常见。

核心思想：用数组模拟链表

为每个顶点 维护一个 指向其第一条出边的指针（索引），然后每条边记录 下一条从同一起点出发的边 的索引。

需要以下几个数组：

• head[N]：存储每个顶点 的第一条边的索引（在边集数组中的下标）。初始时通常填充为 -1（表示没有出边）。
• edge[M]：存储边的目标顶点 。
• next[M]：存储与当前边 起点相同 的下一条边的索引。next[i] 指向的是与第 条边起点相同的下一条边在 edge 和 next 数组中的索引。
• weight[M]（可选）：存储边的权重 。
• idx（或 cnt）：一个计数器，表示当前已经存储了多少条边，也用作新边的索引。

加边操作 add(u, v, w) 的逻辑：

1. 记录新边的信息：edge[idx] = v, weight[idx] = w。
2. 设置新边的 next 指针：新边的下一条边应该是原来 的第一条边，即 next[idx] = head[u]。
3. 更新 的第一条边指针：现在新边是 出发的第一条边了，所以 head[u] = idx。
4. 增加边计数器：idx++。

这个过程类似于在链表头部插入新节点。

实现方式与代码示例

题意概括: 读取 个点 条边的带权有向图信息，并使用链式前向星存储。然后演示如何遍历一个点的所有出边。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5; // 点数上限
const int M = 2e5 + 5; // 边数上限 (无向图可能需要两倍空间)

int head[N]; // head[u]: 顶点 u 的第一条边的索引
int edge[M]; // edge[i]: 第 i 条边的终点
int next_edge[M]; // next_edge[i]: 与第 i 条边同起点的下一条边的索引
int weight[M]; // weight[i]: 第 i 条边的权重 (可选)
int idx; // 当前已使用的边的索引，从 0 开始

// 初始化链式前向星
void init() {
    memset(head, -1, sizeof(head)); // 所有头指针初始化为 -1
    idx = 0; // 边计数器归零
}

// 添加一条从 u 到 v，权重为 w 的有向边
void add(int u, int v, int w) {
    edge[idx] = v;       // 存储终点
    weight[idx] = w;     // 存储权重
    next_edge[idx] = head[u]; // 新边的 next 指向旧的 head
    head[u] = idx;       // 更新 u 的 head 为当前新边的索引
    idx++;               // 边计数器加 1
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    init(); // 初始化

    // 读入边信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w); // 添加有向边

        // 如果是无向图，需要添加反向边
        // add(v, u, w);
    }

    // 示例: 遍历顶点 u 的所有出边 (邻居)
    int u_to_traverse = 1; // 假设遍历顶点 1 的邻居
    // cout << "Edges starting from node " << u_to_traverse << ":\n";
    for (int i = head[u_to_traverse]; ~i; i = next_edge[i]) {
        // ~i 是一种检查 i != -1 的简洁写法
        int v = edge[i];  // 获取终点
        int w = weight[i]; // 获取权重
        // cout << "  -> Node " << v << " (Weight " << w << ")\n";
    }

    return 0;
}

代码解释:

• init() 函数用于初始化 head 数组为 -1 和重置 idx。**每次处理新的图数据前必须调用 init()**。
• add(u, v, w) 函数实现了链式前向星的核心加边逻辑。
• 遍历顶点 的邻居：从 head[u] 开始，沿着 next_edge 链条不断访问，直到索引变为 -1。for (int i = head[u]; ~i; i = next_edge[i]) 是标准遍历写法，~i 等价于 i != -1。

时空复杂度分析

• 空间复杂度： 。需要 个整数存 head，以及 （或 ）个整数分别存 edge, next_edge, weight。与 vector 邻接表同阶，但常数因子可能更小（都是 int，没有 vector 或 pair 的开销）。
• 时间复杂度：
  • 初始化： (如果使用 memset)。
  • 添加边： 。
  • 查询边 是否存在/获取权重： 。需要遍历 的出边链表。
  • 遍历顶点 的所有邻居： 。效率很高。
  • 计算顶点 的出度： 。需要遍历一次链表来计数。不如 vector 的 size() 方便。
  • 计算顶点 的入度： 同 vector 邻接表，需要遍历所有边或额外维护。

优缺点与适用场景

优点：

• 空间效率高 ()，且常数因子通常比 vector 实现略小。
• 所有操作都是 或 ，性能稳定。
• 纯数组实现，内存连续性可能更好，理论上缓存命中率可能更高（但在现代 C++ 编译器优化下，vector 的性能通常也非常好）。
• 易于实现边的成对存储（见下文）。

缺点：

• 实现相对 vector 邻接表稍复杂，容易出错（如忘记初始化 head，idx 管理错误）。
• 需要预先估计边的数量 来确定数组大小，不够灵活。如果边数超过预设大小会导致越界。
• 删除边操作困难（需要修改链表结构）。
• 获取出度不如 vector 方便。

适用场景：

• 对内存或常数时间效率有极致要求的场合。
• 需要利用边成对存储特性的算法（如网络流）。
• 习惯 C 语言风格或在不支持 vector 的环境。
• 一些模板库或历史代码中使用。

与 vector 邻接表的比较

特性	vector 邻接表	链式前向星
实现复杂度	较低 (利用 STL)	稍高 (手动管理数组和索引)
空间复杂度		(常数可能略小)
加边时间	摊还
遍历邻居
查边
获取出度	(.size())
灵活性	高 (动态大小)	低 (需预估 M)
内存管理	STL 自动	手动 (数组)
常数效率	通常很好	可能微弱领先，依赖实现和环境

结论： 对于大多数题目，**vector 实现的邻接表是首选**，因为它更简洁、灵活且不易出错，性能也足够好。只有在特定情况（如追求极限性能、内存卡得很紧、需要成对边特性）下，链式前向星才成为必要的选择。

妙用：成对存储边 (idx ^ 1)

在处理无向图或需要反向边的有向图算法（如网络流中的残差图）时，链式前向星有一个常用技巧：成对加边。

假设我们添加一条从 到 的边（索引为 idx），紧接着添加一条从 到 的反向边（索引为 idx+1）。那么，这两条边的索引就是连续的偶数和奇数（例如 0 和 1, 2 和 3, …）。

利用位运算 ^ (异或)，我们可以通过一条边的索引快速找到其反向边的索引：

• 如果 i 是偶数，i ^ 1 = i + 1。
• 如果 i 是奇数，i ^ 1 = i - 1。

因此，i ^ 1 总是能得到与 i 成对的那条边的索引。

实现:

1. 让 idx 从 0 或 2 开始（通常从 0 开始）。
2. 添加边 时，调用 add(u, v, w)，此时边索引为 idx。
3. 紧接着添加反向边 （ 可能是 ，也可能是 0 或其他值，取决于算法需求），调用 add(v, u, w')，此时边索引为 idx+1。
4. 在算法中，如果知道一条边的索引是 i，那么它的反向边索引就是 i ^ 1。

代码示例 (加边部分):

// idx 从 0 开始
void add_pair(int u, int v, int w, int w_rev) {
    // 正向边 u -> v
    edge[idx] = v; weight[idx] = w; next_edge[idx] = head[u]; head[u] = idx++;
    // 反向边 v -> u
    edge[idx] = u; weight[idx] = w_rev; next_edge[idx] = head[v]; head[v] = idx++;
}

// 在主函数中调用:
// 对于无向图:
// add_pair(u, v, w, w); // 正反权重相同
// 对于网络流 (假设容量为 c):
// add_pair(u, v, c, 0); // 正向边容量 c, 反向边初始容量 0

这种技巧在网络流算法（如 Dinic, ISAP）中非常关键，用于方便地查找和修改反向边的容量。

6. 如何选择合适的存储方式？—— 决策指南

选择哪种存储方式，需要综合考虑多个因素。

关键考量因素：点数、边数、操作类型

1. 点数 N 和 边数 M：

   • N 很大 (e.g., )： 邻接矩阵 ( 空间) 基本排除。必须使用邻接表或链式前向星 ( 空间)。
   • N 很小 (e.g., )： 邻接矩阵空间可行。
   • 图的稠密度：
     • 稀疏图 ()： 邻接表/链式前向星空间优势明显，且遍历邻居效率高。**首选邻接表 (vector)**。
     • 稠密图 ()： 邻接矩阵空间尚可。如果算法 主要操作是检查边是否存在，邻接矩阵 查询有优势。但如果算法 主要操作是遍历邻居，即使是稠密图，邻接表/链式前向星的 （此时 ）也与邻接矩阵的 相当，但空间可能更优（如果 略小于 ）。

2. 主要操作类型：

   • 频繁查询 是否存在/获取权重： 邻接矩阵 最佳。邻接表/链式前向星 较慢。
   • 频繁遍历节点 的所有邻居： 邻接表/链式前向星 最佳。邻接矩阵 较慢。
   • 需要获取节点出度： vector 邻接表 最佳。链式前向星和邻接矩阵 或 。
   • 需要快速找到反向边（如网络流）： 链式前向星的 idx ^ 1 技巧很方便。vector 邻接表需要额外存储反向边索引，稍麻烦。
   • 需要动态加边/删边： vector 邻接表加边方便，删边较慢（需要查找和擦除）。链式前向星加边快，删边困难。邻接矩阵加/删（置INF）都很快。

竞赛场景下的经验法则

• 看到 N 很大（如 ），基本确定用邻接表 (vector) 或链式前向星。
• 默认选择 vector 邻接表。 它最通用、灵活、易于实现。只有遇到特殊情况再考虑其他。
• 如果 N 很小（几百），且题目涉及所有点对关系（如 Floyd），可以考虑邻接矩阵。
• 如果题目是网络流或者需要频繁、快速地访问反向边，可以考虑链式前向星。
• 如果内存限制非常苛刻，链式前向星可能比 vector 稍微节省一点内存（但差别通常不大）。
• 时间限制非常苛刻，且常数因素可能成为瓶颈时，可以尝试链式前向星（但优先优化算法本身，存储方式的常数差异通常不是决定性因素）。

总结： vector 邻接表是你在 ICPC 赛场上的 “主力武器”，熟练掌握它至关重要。了解邻接矩阵和链式前向星的特点，能在特定场景下做出更优选择。

7. 进阶话题与竞赛技巧

存储额外信息

有时边上需要存储多种信息，例如 {终点, 权重, 边的ID, 边的类型}。

• vector 邻接表： 使用 vector<tuple<int, int, int, int>> adj[N]; 或者定义一个结构体 struct Edge { int v, w, id, type; }; vector<Edge> adj[N];。非常灵活。
• 链式前向星： 添加额外的数组，如 edge_id[M], edge_type[M]。需要同步管理所有数组。

隐式图的处理

有些题目并不直接给出图的边，而是通过规则定义。例如：

• 网格图： 节点是格子 ，边是相邻格子间的移动。不需要显式存储整个图，可以在需要时（如 BFS/DFS/Dijkstra）动态计算一个格子的邻居。
• 状态转移图： 节点是问题的状态（如 (位置, 已访问集合)），边是合法的状态转移。这种图可能非常大，通常也是动态生成邻居，而不是预先存储。

对于隐式图，你不需要选择存储方式，而是要实现一个 生成邻居的函数 get_neighbors(state)。

vector 预分配空间 (reserve)

如果能预知一个节点的邻居数量上限或者平均数量，可以使用 adj[u].reserve(k) 为 vector 预留空间，避免多次动态内存重新分配，可能带来微小的性能提升。但在大多数情况下，这个优化不是必需的。

// 假设我们知道每个点的度数不会超过 D
for (int i = 1; i <= n; ++i) {
    adj[i].reserve(D); // 预分配空间
}
// ... 之后 add_edge ...

内存优化考量

• 对于无权图，使用 vector<int> adj[N] 而不是 vector<pair<int, int>>。
• 如果边权很小，可以使用 short 或 char 类型存储权重（注意范围）。
• 链式前向星使用的纯数组可能比 vector<pair<...>> 结构在内存占用上略有优势。

8. 实战演练：典型问题与代码实现

我们来看一个简单问题，演示如何使用 vector 邻接表。

问题：图的遍历（寻找连通块）

题意概括: 给定一个 个点 条边的 无向图。计算图中有多少个连通块。

思路: 使用 DFS 或 BFS。遍历所有节点，如果一个节点尚未被访问，则从该节点开始进行一次 DFS/BFS，标记所有能到达的节点为已访问，并将连通块计数器加一。

题解代码（vector 邻接表）

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5;

vector<int> adj[N]; // 无向无权图，邻接表存邻接点即可
bool vis[N];       // 访问标记数组
int n, m;

// 添加无向边
void add(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // 无向图要加两条边
}

// 深度优先搜索
void dfs(int u) {
    vis[u] = true; // 标记当前节点已访问
    for (int v : adj[u]) { // 遍历 u 的所有邻居
        if (!vis[v]) {    // 如果邻居 v 未访问
            dfs(v);       // 递归访问 v
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    // 读入边信息
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }

    int cnt = 0; // 连通块计数器
    for (int i = 1; i <= n; ++i) { // 遍历所有节点
        if (!vis[i]) { // 如果节点 i 还未被访问过 (属于新的连通块)
            dfs(i);   // 从 i 开始 DFS，访问整个连通块
            cnt++;    // 连通块数量加 1
        }
    }

    cout << cnt << endl; // 输出连通块数量

    return 0;
}

代码解释:

• 使用 vector<int> adj[N] 存储无权图。
• add(u, v) 函数同时添加 u->v 和 v->u 的边。
• dfs(u) 函数实现了标准的深度优先搜索逻辑。
• 主函数通过遍历所有节点，对未访问过的节点启动 dfs 来找到并标记一个完整的连通块，同时计数。

复杂度分析:

• 建图时间复杂度： （初始化 个 vector + 次 push_back）。
• DFS 时间复杂度： 每个节点和每条边最多被访问常数次（对于无向图是两次），所以总时间复杂度是 。
• 空间复杂度： （存储邻接表和 vis 数组）。

这个例子展示了 vector 邻接表在处理标准图遍历问题时的简洁和高效。

9. 写在最后

图的存储，是图论算法的基石。虽然邻接矩阵、邻接表（vector 实现）和链式前向星是最核心的三种方式，但真正的精通，在于理解它们各自的原理、时空特性、实现细节，并能在不同的问题背景下，根据实际需求（点数、边数、图的稠密度、后续算法操作）做出最明智的选择。

• 务必熟练掌握 vector 邻接表的实现和使用，这是你们最常用的工具。
• 理解链式前向星的原理和实现，特别是在网络流等特定场景下的优势（如 idx ^ 1）。
• 了解邻接矩阵的适用范围（小规模稠密图或需 查边）。
• 培养根据问题特点选择存储方式的决策能力。

选择合适的存储方式，只是万里长征的第一步。后续的图算法学习（BFS, DFS, 最短路, 生成树, 网络流, 图匹配等）都将建立在这个基础上。