做过图论题的人应该都有这种体验：不少题目表面包装得花里胡哨，内核却是同一套经典算法。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. 基于邻接表的染色实现：从零到AC
3.1 数据结构选型：邻接矩阵还是邻接表
做题第一步通常是建图。PA7这类题N的范围往往到1e5甚至更大，M也能到2e5以上，这种情况下邻接矩阵是绝对的禁区——一个N乘N的二维数组内存直接爆掉，哪怕N只有1e4也存不下。
邻接表是最自然的选择。C++里我一般用vector<int> g[N+1]，因为是无向图，所以读入每条边时两端各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表示两种频率：
vector<int> color(n + 1, 0); auto bfs = [&](int start) -> bool { queue<int> 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(V+E)是怎么来的
每次BFS里，每个节点只会入队出队一次，所以节点访问的总代价是O(V)。对于边来说，每条边u-v在遍历u时会访问一次v，遍历v时会访问一次u，一共被访问两次，总代价O(E)。外层for循环虽然遍历了所有节点，但每个节点只作为BFS起点一次，所以不改变整体复杂度。
因此算法总时间复杂度是O(V+E)，空间复杂度也是O(V+E)——邻接表存了所有边，color数组和队列各占O(V)。这个复杂度在1e5、2e5级别的数据下完全可以跑进1秒。
4.2 特殊数据与极端情况实测
我习惯在写完之后跑几组特殊数据验证正确性：
- 单个节点、没有边：是二分图，输出Yes。
- 两个节点、一条边：1和2颜色相反，输出Yes。
- 三个节点的三角形：必然冲突，输出No。
- 四个节点的偶数环1-2-3-4-1：BFS染色为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种频率可选，求任意合法分配”，事情就完全不一样了。K=3时，图的三色问题已经是NP完全问题——没有已知的多项式时间解法，竞赛里除非数据范围极小，否则不会让你硬做。
就算K比较小，比如K=4，一般图着色依然是超级困难的问题。所以下次再看到“给点的邻域分资源、求最少颜色数”之类的题，先别急着套着色模板，想一想题目是否加了隐藏限制：是不是树？是不是二分图？是不是平面图？是不是区间图？这些特殊图类往往有各自的线性或多项式解法。
5.3 我的调试经验与一点技巧
最后说点实际的。我在PA7这道题上第一次提交失败，不是算法写错，而是忘记处理多组输入间的color重置。那次调了一个多小时，最后打印中间变量才发现第二组数据继承了第一组的颜色值。
这里分享两个我常用的调试技巧：
第一个是在BFS起点染色后，顺手打印一遍该连通分量的节点和颜色。这样你能肉眼确认每个分量是否被正确遍历，也方便定位是哪条边触发冲突。
第二个是构造一个包含“两个连通分量、其中一个为三角形”的小测试数据，这个数据能同时验证外层for和冲突检测两条逻辑。如果这个数据能过，说明核心框架基本没问题。
如果你正在卡PA7，我强烈建议你先手动把样例数据画成图，然后模拟一遍BFS染色过程，再去看代码。很多时候，卡住的不是代码，而是脑子里的图模型没搭起来。图论题的乐趣也正在于此——它考验的往往不是你会不会背算法，而是你能不能看穿故事外壳下的数学结构。
