做过图论题的人应该都有这种体验不少题目表面包装得花里胡哨内核却是同一套经典算法。PA7这道“无线广播(Broadcast)”就属于典型例子——题目用一堆广播站互相干扰当故事背景实际考察的却是二分图判定。我第一次做这题的时候也被带偏过以为要搞什么复杂的频率规划读完数据范围才发现核心就一句话判断每个连通分量能否用两种频率完成无冲突分配。这篇笔记我会从题目建模开始把为什么答案等于二分图判定、染色法的原理、邻接表实现、复杂度分析以及常见坑位一次讲清楚。无论你是刚开始刷图论的初学者还是想快速温习二分图判定的老手照着这个思路走基本就能从零到AC。1. 先看PA7这道题它到底让你求什么1.1 题目表面广播站之间不能互相干扰无线广播题的描述通常长这样有N个广播站站与站之间存在干扰关系给定M对“干扰对”意思是这两个站如果使用相同频率就会互相干扰现在要求给每个站分配一个频率使得任意一对存在干扰关系的站频率都不相同。题目一般有两种问法。第一种问“最少需要几种频率才能完成分配”第二种问“给定两个频率是否存在合法分配方案”。PA7这道题纠结的其实是第二种——它给的频率池通常只有两个选择比如频率A和频率B让你判断能不能安排。这里就有个第一眼容易踩的坑看到“最少几种频率”就以为要解一般图着色问题。实际上只要频率池限定为两种题目就从“NP难的着色问题”一下子降级成了“线性可解的二分图判定问题”。很多同学卡住往往就是没抓住这个限制条件。1.2 把干扰关系翻译成一张图建模部分其实很直白每个广播站看作一个顶点。每对干扰关系看作一条无向边。两种频率看作两种颜色比如颜色1和颜色-1。题意变成能否给每个顶点染上两种颜色之一使得每条边的两个端点颜色不同。这个“每条边两端颜色不同”的染色要求就是二分图的定义。换句话说题目给出的图如果是二分图就能用两个频率完成分配如果不是二分图就无论如何都会产生冲突。拿一个小例子体会一下。假设有3个广播站干扰关系是(1,2)和(2,3)那么可以这样分配站1用A站2用B站3用A完美规避干扰。但如果在(1,2)和(2,3)之外再加一条(1,3)三个站两两干扰这时无论怎么用A和B去染总有一条边的两端同色。这种三角形结构就是二分图判定的核心障碍。1.3 为什么正解是“二分图判定”而不是别的我见过有人拿到这题后去建图跑了最小生成树也有人试图用贪心顺序给节点逐个分配频率这些思路在部分数据上可能碰巧能过但都属于走偏了。根本原因在于二分图判定问题有一个数学上非常干净的性质——“能用两种颜色完成染色”和“图中不存在奇环”是等价的。奇环就是长度为奇数的环比如三角形、五边形。如果一个图存在奇环两种颜色无论如何都染不完如果不存在奇环则一定可以二分。所以PA7的正解思路非常固定读入N和M建邻接表。对每个连通分量做染色BFS或DFS。染色过程中发现任意边的两端颜色相同则说明存在奇环输出“不能完成分配”。所有连通分量都染色成功输出“可以完成分配”。这也是我想提醒你的地方做图论题先别急着上手写代码先拆清楚题目等价于哪个经典模型。这一步想通了代码量其实非常小。2. 二分图判定的核心原理染色法的“为什么”2.1 矛盾的本质奇环为什么这么致命我们得稍微深入一点理解“为什么存在奇环就必然无法染成两色”。这听起来像结论但如果你能在脑子里画一遍后面写代码时就不容易写错。假设有一条长度为3的环A—B—C—A。给A染成颜色1那么B必须染颜色-1因为和A有边C必须染颜色1因为和B有边。这时候问题来了C和A之间也有一条边但C的颜色和A一样都是1于是冲突。同理长度为5、7、9的环都会在“绕了一圈之后”回到起点时产生颜色反转。你可以把染色过程想象成沿着边走每走一步颜色翻转一次。路径长度为偶数时颜色翻转偶数次回到原色长度为奇数时翻转奇数次变成反色而边的两端又不能同色于是矛盾。所以二分图的本质可以概括成一句话图中要么没有环要么所有环的长度都是偶数。2.2 BFS层数与对偶性为什么要逐层遍历理解了奇环之后就该思考“怎么在代码里检测奇环”。最常用的做法就是给图做BFS分层染色。从某个起点开始起点染颜色1记为第0层。所有与起点直接相邻的节点染颜色-1记为第1层。与第1层相邻且未染色的节点染颜色1记为第2层。以此类推。你会发现如果图是二分图那么同一层的所有节点颜色相同相邻层的颜色恰好相反。这个“层数奇偶决定颜色”的性质非常直观第0层、第2层、第4层都是颜色1第1层、第3层、第5层都是颜色-1。那什么时候会出问题就是BFS遍历到一条边发现它的两个端点已经被染色而且颜色相同。这条边要么连接同一层内的两个节点要么连接相差偶数层的两个节点。无论哪种情况都说明图中存在一条长度为奇数的路径闭环也就是奇环。用BFS而不是DFS的一个额外好处是BFS天然按层推进你可以在调试时直接打印每个节点的层数和颜色很容易发现是哪条边引爆了冲突。2.3 一个矛盾点就能否定全图为什么?写代码时会有一个疑问我只从一个连通分量里发现了冲突能不能立刻判定整张图不行答案是能。因为每个连通分量是独立的只要有一个连通分量不是二分图整个图的“两色合法分配”就不存在。反过来如果一个连通分量里所有边都满足两端异色那就说明这个连通分量成功构造出了合法的二染色。把所有连通分量的染色结果拼在一起就是整张图的一个合法染色方案。所以整个算法可以写成依次处理每个连通分量任何一个分量染色失败就终止全部成功则输出可行。这也解释了后面代码里为什么要有一个外层for循环——就是为了确保不遗漏任何一个连通分量。3. 基于邻接表的染色实现从零到AC3.1 数据结构选型邻接矩阵还是邻接表做题第一步通常是建图。PA7这类题N的范围往往到1e5甚至更大M也能到2e5以上这种情况下邻接矩阵是绝对的禁区——一个N乘N的二维数组内存直接爆掉哪怕N只有1e4也存不下。邻接表是最自然的选择。C里我一般用vectorint g[N1]因为是无向图所以读入每条边时两端各push一次for (int i 0; i m; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); }有人会问要不要用set去重。通常不用因为染色算法的正确性不受重边影响。重边只会让同一条边被重复检查几次浪费一点常数时间不会造成误判。真的担心重边很多可以后续排序去重再建图但普通题目用不上。3.2 主循环框架外层for循环为什么不能省下面是PA7二分图判定最核心的代码框架我用颜色数组color的0表示未染色1和-1表示两种频率vectorint color(n 1, 0); auto bfs [](int start) - bool { queueint q; color[start] 1; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (color[v] 0) { color[v] -color[u]; q.push(v); } else if (color[v] color[u]) { return false; } } } return true; }; bool ok true; for (int i 1; i n; i) { if (color[i] 0) { if (!bfs(i)) { ok false; break; } } } cout (ok ? Yes : No) \n;注意看主循环从1到n遍历所有节点只要发现某个节点没被染色就用它当起点做一次BFS。这个外层循环绝对不能省。原因很简单图不一定是连通的。如果图分成两个或多个互不相连的连通分量你只从节点1开始BFS节点1所在的分量虽然染色成功但另一个分量根本不会被访问到。这个坑我在第一次写类似题目时就踩过——样例、小数据都过了一到大数据就错后来才发现是漏处理了第二个连通分量。3.3 冲突检测的两种写法与边界条件BFS内部检查冲突有两种等价写法写法一if (color[v] 0) { color[v] -color[u]; q.push(v); } else if (color[v] color[u]) { return false; }写法二if (color[v] ! -color[u]) { return false; }第二种写法必须配合“如果color[v]0需要先染色”的分支否则会把未染色节点直接判成冲突。所以建议新手用第一种逻辑更清楚。边界情况也需要留意自环如果有一条边(u,u)那么遍历到u时v也是u。此时color[v]color[u]1必然冲突能被正确检测到。孤立点没有任何边的点会触发一次独立的BFS但BFS里没有邻居直接返回true。不影响答案。重边同一对节点之间有多条边重复检查会导致多跑几次if判断但不会改变结果。3.4 Python与C实现对比与性能注意有些同学习惯用Python刷题逻辑完全一样就是要注意两点一是用collections.deque而不是list当队列否则pop(0)是O(n)操作大数据下会超时二是Python的递归深度限制比较小所以不建议用递归DFS用BFS或者显式栈更安全。下面是一个Python版本的参考实现from collections import deque def solve(): n, m map(int, input().split()) g [[] for _ in range(n 1)] for _ in range(m): u, v map(int, input().split()) g[u].append(v) g[v].append(u) color [0] * (n 1) def bfs(start): q deque([start]) color[start] 1 while q: u q.popleft() for v in g[u]: if color[v] 0: color[v] -color[u] q.append(v) elif color[v] color[u]: return False return True for i in range(1, n 1): if color[i] 0: if not bfs(i): print(No) return print(Yes)C和Python在这个题目上性能差异主要来自输入和队列操作。如果数据量来到1e5级别Python用sys.stdin.buffer.read()优化输入会更好C则记得关闭同步流或者直接改用scanf。排序这些都不是关键别因为IO把题写TLE了。4. 复杂度与正确性为什么这个解是“安全的”4.1 时间复杂度O(VE)是怎么来的每次BFS里每个节点只会入队出队一次所以节点访问的总代价是O(V)。对于边来说每条边u-v在遍历u时会访问一次v遍历v时会访问一次u一共被访问两次总代价O(E)。外层for循环虽然遍历了所有节点但每个节点只作为BFS起点一次所以不改变整体复杂度。因此算法总时间复杂度是O(VE)空间复杂度也是O(VE)——邻接表存了所有边color数组和队列各占O(V)。这个复杂度在1e5、2e5级别的数据下完全可以跑进1秒。4.2 特殊数据与极端情况实测我习惯在写完之后跑几组特殊数据验证正确性单个节点、没有边是二分图输出Yes。两个节点、一条边1和2颜色相反输出Yes。三个节点的三角形必然冲突输出No。四个节点的偶数环1-2-3-4-1BFS染色为1,-1,1,-1所有边两端异色输出Yes。两个连通分量其中一个三角形一个偶数环外层for会分别处理两个分量三角形分量触发冲突输出No。这些数据虽然简单但能覆盖90%的边界坑。尤其是“多个连通分量”的组合数据是最容易暴露外层for缺失的测试点。4.3 常见错误森林分裂、孤立点、多组数据除了漏掉外层for还有几个高频错误第一个是用DFS递归。图深度大时C递归栈可能爆掉Python更是容易触发递归深度上限。如果非要用DFS请写成显式栈或者给C手动增加栈空间——但BFS它不香吗第二个是多组测试数据时忘记重置color数组。PA7这类练习通常会让你处理多组输入如果color不清空上一次的染色结果会污染这一次的判定。第三个是输入输出优化。N一大cin和cout不加ios::sync_with_stdio(false); cin.tie(nullptr);就会很吃亏。Python同理sys.stdin.readline()远比input()快。第四个是关于孤立点的小陷阱孤立点当然是二分图的一部分它没有边所以染1还是-1都行。代码里因为color[i]0会触发一次空BFS直接返回true这个行为是正确的不需要额外特判。5. 从PA7往外看二分图模型的真实应用5.1 二分图判定的变形题二分图判定本身很少是最终目的它往往是后续算法的一道开胃菜。比如很多“分成两组”的题目本质上就是先做一次二染色冲突关系连边判断能否分成两组使得组内没有冲突。类似的变形我还见过把一群人分成两个队伍朋友关系必须同队敌人关系必须异队。判断电路中的两个信号集合是否存在反馈干扰。判断一个棋盘上的格子能否用两种颜色标记且相邻格子颜色不同。判定无向图是否存在奇环从而判断图是否为二分图。这些题目的共同套路都是把条件翻译成边然后用一遍染色检验。所以PA7不只是一道孤立的小题它是后面一大类“图着色判定”问题的入门砖。5.2 当答案不是2一般图着色为什么难刚才反复提到“两种频率”是这题能做的关键。如果题目炸一下把条件改成“每个站有K种频率可选求任意合法分配”事情就完全不一样了。K3时图的三色问题已经是NP完全问题——没有已知的多项式时间解法竞赛里除非数据范围极小否则不会让你硬做。就算K比较小比如K4一般图着色依然是超级困难的问题。所以下次再看到“给点的邻域分资源、求最少颜色数”之类的题先别急着套着色模板想一想题目是否加了隐藏限制是不是树是不是二分图是不是平面图是不是区间图这些特殊图类往往有各自的线性或多项式解法。5.3 我的调试经验与一点技巧最后说点实际的。我在PA7这道题上第一次提交失败不是算法写错而是忘记处理多组输入间的color重置。那次调了一个多小时最后打印中间变量才发现第二组数据继承了第一组的颜色值。这里分享两个我常用的调试技巧第一个是在BFS起点染色后顺手打印一遍该连通分量的节点和颜色。这样你能肉眼确认每个分量是否被正确遍历也方便定位是哪条边触发冲突。第二个是构造一个包含“两个连通分量、其中一个为三角形”的小测试数据这个数据能同时验证外层for和冲突检测两条逻辑。如果这个数据能过说明核心框架基本没问题。如果你正在卡PA7我强烈建议你先手动把样例数据画成图然后模拟一遍BFS染色过程再去看代码。很多时候卡住的不是代码而是脑子里的图模型没搭起来。图论题的乐趣也正在于此——它考验的往往不是你会不会背算法而是你能不能看穿故事外壳下的数学结构。
