首页/资讯中心/详情

图论建模与二分图判定：从CCPC赛题看DFS/BFS算法实战

图论建模与二分图判定：从CCPC赛题看DFS/BFS算法实战
📅 发布时间：2026/7/25 6:22:31

1. 项目概述：从一道赛题看图的算法实战

最近在带学生备赛，刷到一道挺有意思的题目——P10048 “[CCPC 2023 北京市赛] 图”。这题名起得直白，就叫“图”，但内容可一点都不简单，它考察的是对图论基础概念的深刻理解以及将问题转化为图论模型的能力。很多刚接触信奥（信息学奥林匹克）的同学，一看到“图”就觉得是最短路或者最小生成树，但这道题恰恰跳出了这个定式思维，它更像是一个“图论建模”的思维体操。题目本身描述可能不长，但如何从一段文字描述中，抽丝剥茧，构建出正确的图模型，才是真正的难点，这也是省赛级别题目常见的风格。

这道题适合已经掌握C++基础语法、学过邻接矩阵和邻接表这两种基本存储方式，并了解深度优先搜索（DFS）和广度优先搜索（BFS）的同学进行拔高训练。它不要求你掌握特别高深的算法，但要求你对“图”这个结构本身有灵活的应用能力。接下来，我就结合这道题，和大家深入聊聊如何用C++实现图的相关算法，并拆解这类问题的通用解决思路。我们会从题目分析、模型构建、存储选择、算法设计到代码实现和调试，完整地走一遍。

2. 核心思路拆解：问题本质与图论建模

拿到题目，第一步永远不是急着写代码，而是彻底理解问题，并尝试用自己熟悉的语言（不一定是编程语言，可以是自然语言或图形）重新描述它。对于P10048，我们首先需要解析其核心需求。

通常，这类赛题会给出一个关于若干元素及其之间关系的描述。例如，元素可能是人、任务、城市，关系可能是“认识”、“冲突”、“先后顺序”、“连通”等。题目的问题往往是：是否存在某种满足条件的安排？最多/最少能有多少个？最小的代价是多少？“图”在这里就是一个绝佳的抽象工具：我们把元素抽象成顶点（Vertex），把元素之间的关系抽象成边（Edge）。

2.1 识别顶点与边

这是建模最关键的一步。以一道经典改编题为例：“有N个人和M对敌对关系，请问能否将所有人分成两组，使得每组内部没有敌对关系？” 这里，顶点显然就是“N个人”。而“M对敌对关系”就是连接顶点的边。这样，我们就把一个生活问题转化为了一个图论问题：给定一个无向图，能否将其顶点进行二染色（比如分成红蓝两组），使得任意一条边连接的两个顶点颜色不同？这就是著名的二分图判定问题。

P10048的具体描述需要你仔细阅读，但方法论是通用的。你需要问自己：题目中的“东西”是什么？它们之间的“关系”是什么？这个关系是双向的还是单向的？回答清楚这几个问题，图的模型就呼之欲出了。关系是双向的（如朋友、冲突），就是无向图；关系是单向的（如A赢了B、A必须排在B之前），就是有向图。

2.2 确定图的性质与算法目标

模型建好，接下来要确定图的性质和我们需要解决的问题。

  • 图的类型：是无向图还是有向图？是稀疏图（边数远少于顶点数的平方）还是稠密图？
  • 算法目标：题目是要求我们判断属性（如是否为二分图、是否有环），还是进行遍历（如连通块计数），或是寻找路径（最短路），亦或是进行计算（如满足某条件的顶点对数）？

对于二分图判定这类问题，目标非常明确：遍历整个图，尝试进行染色，如果过程中发现矛盾（即一条边连接的两个顶点被染成了相同颜色），则判定失败。这通常通过DFS或BFS遍历来实现。

2.3 选择合适的数据结构存储图

这是C++实现中非常实际的一步，选择直接影响代码的效率和编写的便捷性。主要有两种主流方式：

  1. 邻接矩阵：用一个二维数组g[N][N]存储，g[i][j] = 1表示顶点i到j有一条边。对于无向图，矩阵是对称的。

    • 优点：直观，检查两点间是否有边非常快（O(1)）。
    • 缺点：空间复杂度高，为 O(N²)。对于顶点数N很大（比如10^5）而边数M较少的稀疏图，会造成巨大的内存浪费，通常不可行。
    • 适用场景：顶点数较少（一般N ≤ 1000）的稠密图。

  2. 邻接表：这是最常用、最通用的存储方式。为每个顶点维护一个链表（在C++中常用vector<int>来模拟），链表中存储与该顶点直接相连的所有邻居顶点。

    • 优点：空间复杂度为 O(N+M)，与实际的顶点数和边数成正比，非常适合稀疏图。遍历某个顶点的所有邻居也非常高效。
    • 缺点：判断任意两点i和j之间是否有边，需要遍历i的邻居链表，最坏情况O(N)。
    • 适用场景：绝大多数情况，尤其是顶点数多、边数相对较少的竞赛题目。

注意：在信奥赛题中，由于数据规模通常较大（N和M可达10^5量级），邻接表（用vector实现）是绝对的首选。P10048也极大概率需要使用邻接表。

3. 算法设计与实现：以二分图判定为例

假设P10048经分析后，核心是二分图判定问题。我们来详细走一遍用C++实现DFS染色的全过程。这里会包含大量实际编码中的细节和技巧。

3.1 数据结构定义与输入处理

首先，我们定义全局的数据结构。由于图的顶点通常从1开始编号，为了方便，我们的数组会开得比最大顶点数稍大一些。

#include <iostream> #include <vector> using namespace std; const int MAXN = 100010; // 根据题目数据范围设定，通常比最大N大一些 vector<int> graph[MAXN]; // 邻接表，graph[i]存储顶点i的所有邻居 int color[MAXN]; // 染色数组，0表示未染色，1和2表示两种颜色 int n, m; // n个顶点，m条边

接下来是输入处理。这是非常模式化的部分，但要注意无向图边的添加方式。

bool input() { // 这里假设题目输入格式为：第一行n, m，接下来m行每行两个整数u, v表示一条边。 if (!(cin >> n >> m)) return false; // 处理多组数据输入结束的情况 // 初始化图，非常重要！特别是处理多组数据时，必须清空。 for (int i = 1; i <= n; ++i) { graph[i].clear(); } for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; // 无向图，边需要添加两次 graph[u].push_back(v); graph[v].push_back(u); } return true; }

实操心得：graph[i].clear()这步在初始化或处理多组数据时至关重要。我曾因为忘记清空，导致上一组数据残留的边混入下一组，调试了半小时才找到这个隐蔽的Bug。对于color数组，我们可以在每次DFS前用memset或循环归零，但更常见的做法是在DFS函数内部判断是否访问过。

3.2 DFS染色核心函数

这是算法的核心。我们从一个未染色的顶点开始，将其染成颜色1，然后递归地遍历它的所有邻居。对于每个邻居：

  • 如果未染色，就将其染成与当前顶点相反的颜色（1->2, 2->1），并继续递归。
  • 如果已染色，则检查其颜色是否与当前顶点相反。如果不是，说明发现冲突，整张图不是二分图。
// 从顶点u开始进行DFS染色，当前顶点u的颜色是c // 返回值：从u开始的子图是否是二分图 bool dfs(int u, int c) { color[u] = c; // 将顶点u染成颜色c int nextColor = (c == 1) ? 2 : 1; // 邻居应该染的相反颜色 // 遍历u的所有邻居顶点v for (int i = 0; i < graph[u].size(); ++i) { int v = graph[u][i]; if (color[v] == 0) { // 邻居v未染色 // 递归染色，如果递归返回false，则直接向上传递失败信号 if (!dfs(v, nextColor)) { return false; } } else if (color[v] == c) { // 邻居v已染色，且颜色与u相同，冲突！ return false; } // 另一种情况：邻居v已染色，且颜色与u相反，是符合要求的，继续检查其他邻居 } return true; // u的所有邻居都检查完毕，没有冲突 }

为什么参数是(int u, int c)？u是当前要处理的顶点，c是这个顶点“应该被染的颜色”。这个颜色是由它的父顶点决定的。在顶层调用时，我们传入一个初始颜色（通常是1）。这种“传入状态”的递归设计非常清晰。

3.3 主逻辑与遍历入口

图可能不是连通图，即由多个连通分量组成。因此，我们需要检查每一个连通分量是否都是二分图。

bool isBipartite() { // 初始化颜色数组，0表示未访问/未染色 // 使用循环+赋值，比memset更安全（避免字节操作可能的问题，虽然这里用int没问题） for (int i = 1; i <= n; ++i) { color[i] = 0; } for (int i = 1; i <= n; ++i) { if (color[i] == 0) { // 找到一个未染色的顶点，说明是一个新连通分量的起点 // 从这个点开始染色，初始颜色设为1 if (!dfs(i, 1)) { // 如果这个连通分量染色失败，整张图就不是二分图 return false; } } } // 所有连通分量都染色成功 return true; } int main() { while (input()) { // 处理多组数据 if (isBipartite()) { cout << "YES" << endl; // 是二分图，满足题目分组要求 } else { cout << "NO" << endl; // 不是二分图，无法满足要求 } } return 0; }

关键点解析：主函数中的for (int i = 1; i <= n; ++i)循环确保了即使图不连通，每个顶点也都会被检查到。color[i]==0是发现新连通分量的标志。

4. 代码实现的深度优化与细节探讨

上面的代码已经可以解决基础问题。但在竞赛中，我们需要考虑效率、鲁棒性和代码的简洁性。下面分享几个进阶技巧。

4.1 邻接表遍历的优化写法

使用C++11的范围for循环（range-based for loop）可以让遍历邻居的代码更简洁、更不易出错。

bool dfs(int u, int c) { color[u] = c; int nextColor = 3 - c; // 一个小技巧：如果c是1，3-1=2；如果c是2，3-2=1。 for (int v : graph[u]) { // 更清晰的遍历方式 if (color[v] == 0) { if (!dfs(v, nextColor)) return false; } else if (color[v] == c) { return false; } } return true; }

3-c这个技巧比三元运算符? :在思维上更直接。范围for循环避免了手动管理下标i和调用graph[u].size()，减少了出错概率。

4.2 使用BFS实现染色

除了DFS，BFS（广度优先搜索）同样可以用于二分图判定。BFS使用队列，是非递归的，对于深度很大的图，可以避免递归栈溢出的风险。

#include <queue> bool bfs(int start) { queue<int> q; q.push(start); color[start] = 1; // 起始点染颜色1 while (!q.empty()) { int u = q.front(); q.pop(); int nextColor = 3 - color[u]; for (int v : graph[u]) { if (color[v] == 0) { color[v] = nextColor; q.push(v); } else if (color[v] == color[u]) { return false; } } } return true; } bool isBipartiteBFS() { for (int i = 1; i <= n; ++i) color[i] = 0; for (int i = 1; i <= n; ++i) { if (color[i] == 0) { if (!bfs(i)) return false; } } return true; }

BFS的思路是“层层推进”。它和DFS在判断二分图这个问题上是等价的，时间复杂度都是O(N+M)。你可以根据个人习惯或题目特性选择。

4.3 处理大规模输入的效率问题

当顶点数N非常大时（比如10^5），即使使用邻接表，一些细微的操作也可能成为瓶颈。

  • cin/cout与scanf/printf：在需要读入大量数据（10^5量级以上）时，C语言的scanf和printf通常比cin/cout快。可以在代码开头加上ios::sync_with_stdio(false); cin.tie(0);来关闭C++流与C标准流的同步，从而大幅提升cin/cout的速度，使其接近scanf。但注意，一旦加了这句，就不要混用cin/cout和scanf/printf。
  • vector的reserve方法：如果你能预估每个顶点大致的邻居数，可以在建图前使用graph[i].reserve(estimated_size)来预留内存空间，减少push_back时动态扩容的开销。不过这在竞赛中通常不是必须的，vector的自动扩容机制已经足够高效。

5. 常见问题排查与调试技巧实录

即便思路清晰，实际编码和调试中也会遇到各种问题。下面是我和学生们在刷这类图论题目时，踩过的一些“坑”和解决方法。

5.1 多组数据初始化不全

这是最最常见的错误，没有之一。

  • 症状：第一组数据结果正确，从第二组开始结果随机错误。
  • 原因：只清空了graph邻接表，但忘记了清空color等全局状态数组；或者反过来。
  • 解决方案：养成编写init()函数的习惯，在每组数据开始处理时，显式地重置所有用到的全局数据结构。
    void init() { for (int i = 1; i <= n; ++i) { graph[i].clear(); color[i] = 0; // 或其他标记数组 } // 其他需要重置的变量... }
    在input()函数中或读取n, m后立即调用init()。

5.2 递归深度过大导致栈溢出

  • 症状：程序在某个大数据点运行时异常终止（如Segmentation Fault），但小数据正常。
  • 原因：图是一条长长的链（例如100000个顶点连成一条线），使用DFS递归会递归100000层，超出系统默认的栈空间限制。
  • 解决方案：
    1. 改用BFS：BFS使用显式的队列，不存在递归栈溢出问题。
    2. 手动设置栈空间（竞赛环境不一定允许）：有些OJ支持编译指令。
    3. 写非递归DFS：使用栈模拟递归过程，但代码较复杂。对于二分图判定，直接换用BFS是最简单有效的。

5.3 顶点编号从0开始还是从1开始？

  • 问题：题目有时顶点编号从0开始，有时从1开始。我们的数组通常从下标0开始。
  • 解决：统一转换到从1开始处理是最稳妥的。在读入边(u, v)后，执行u++; v++;，这样所有顶点在数组中的下标范围就是[1, n]，与我们的循环for(int i=1; i<=n; ++i)完美匹配。这能避免大量的边界条件判断错误。

5.4 自环和重边的处理

  • 自环：一条边连接同一个顶点。在二分图判定中，如果存在自环，那么这个顶点必须同时和自己颜色不同，这是不可能的，所以只要存在自环，就一定不是二分图。需要在建图时或遍历前进行特判。
  • 重边：两条相同的边。对于邻接表，存储重边不影响DFS/BFS染色的正确性，因为算法逻辑是检查“颜色是否相同”，重边只会重复检查一次，结果不变。但重边会占用额外空间。如果题目明确说“无重边”，我们可以使用set或建图时检查来去重，但通常用vector直接存即可，除非空间特别紧张。

针对自环的特判增强代码：

bool input() { // ... 读取n, m init(); bool hasSelfLoop = false; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; if (u == v) { hasSelfLoop = true; // 记录存在自环 // 即使有自环，边也需要正常添加吗？对于染色算法，添加自环会导致dfs中自己发现自己颜色相同，直接返回false。 // 但为了逻辑清晰，我们可以选择不添加，因为我们已经知道结果了。 // 这里我们选择仍然添加，让dfs过程去发现矛盾。 } graph[u].push_back(v); graph[v].push_back(u); // 如果是无向图 } // 如果题目要求输出具体分组，自环需要提前判断。 // 如果只是判断YES/NO，可以交给dfs处理。 return true; } // 在isBipartite函数中，可以先判断hasSelfLoop，快速返回false。

5.5 调试技巧：小数据画图模拟

当程序结果不对时，最有效的方法不是盯着代码看，而是：

  1. 构造一个小的测试用例（比如n=4, m=3）。
  2. 在纸上画出对应的图。
  3. 用笔和纸模拟你的算法（DFS或BFS），一步步写出color数组的变化。
  4. 再让程序跑这个测试用例，在关键位置（如dfs函数入口、发现冲突时）打印日志，对比你的手动模拟和程序实际执行过程。
  5. 使用IDE（如VSCode）或编辑器的调试功能，单步跟踪，观察变量值。

例如，在dfs函数里加一句调试输出：

bool dfs(int u, int c) { cout << "dfs: u=" << u << ", set color=" << c << endl; // 调试输出 color[u] = c; // ... 其余代码 }

这能帮你清晰地看到递归的路径和染色顺序，快速定位逻辑错误。

6. 从P10048延伸：图论问题的通用解题框架

通过这道题，我们可以总结出一个解决图论建模问题的通用框架，这个框架能应用到很多题目上。

第一步：问题抽象与建模

  • 仔细读题，明确“顶点”是什么，“边”代表什么关系。
  • 判断是有向图还是无向图。
  • 思考图可能具有的性质（是否需要考虑权重？边是否有特殊属性？）。

第二步：数据结构与算法选型

  • 存储：根据顶点数N和边数M，决定使用邻接矩阵（N小）还是邻接表（N大，通用）。
  • 算法：根据问题目标选择。
    • 判断连通性、染色、简单遍历 ->DFS/BFS
    • 单源最短路径（边权非负）->Dijkstra
    • 单源最短路径（有负权边）->Bellman-Ford / SPFA
    • 所有点对最短路径 ->Floyd
    • 最小生成树 ->Kruskal / Prim
    • 拓扑排序 ->基于BFS的Kahn算法 / DFS
    • 强连通分量 ->Kosaraju / Tarjan

第三步：核心函数实现

  • 将选定的算法（如DFS染色、BFS层次遍历）封装成清晰的函数。
  • 注意递归边界条件、访问标记的设置与检查。

第四步：主逻辑整合

  • 处理图可能不连通的情况（循环检查所有未访问顶点）。
  • 整合输入输出，处理多组数据（记得初始化！）。

第五步：测试与调试

  • 用样例测试。
  • 构造边界用例测试（n=0, n=1, m=0， 极大图，链状图，星型图）。
  • 使用打印日志或调试器排查问题。

回到P10048 “[CCPC 2023 北京市赛] 图”这道题，它很可能就是这样一个流程的完美演练。题目描述会引导你建立某个模型（可能是二分图，也可能是检查奇环、甚至是更复杂的约束满足问题），然后你需要运用上述的框架去解决它。真正的难点在于第一步——如何从题目文字中精准地抽象出图模型。这需要大量的练习和积累。

刷题时，不要满足于AC（Accept）。AC之后，去看看别人的题解，学习不同的建模视角和更优美的代码实现。尝试用BFS再写一遍，或者思考如果数据范围变大（N=10^6）该如何优化。把这些思考和尝试记录下来，才是刷题提升的关键。图论是信奥和算法竞赛的基石之一，把这部分基础打扎实，后面遇到更复杂的网络流、树上问题、图论动态规划时，你才会更有底气。