如果你刷题刷到一个叫“无线广播(Broadcast)”的题目第一反应多半是网络工程里的组播协议或者Linux广播风暴但真正打开题面才发现这是一道非常典型的二分图判定题。题目会给你一堆广播发射站以及哪些站点之间互相干扰要求判断能不能只用两个频率把互相干扰的站点全部隔开。看起来像模拟做起来是图论基本功建图、遍历、染色、奇环判定还顺带考验你对非连通图的处理能力。这篇文章就把这道题从读题到AC的完整链路拆开讲。无论你是正在刷图论入门、刚学会BFS和DFS想找题练手还是样例过了交上去却一直WA都能从下面几个部分里找到对应的排查思路。1. 从“广播频率冲突”看这道题到底在问什么1.1 题面背后的图论模型把每个发射站当成一个点两个站如果会互相干扰就在它们之间连一条无向边。每个站点只能被分配两种频率之一如果一条边的两个端点被安排了同一种频率那说明这两个互相干扰的站还在同一个频道里方案直接失败。所以原问题就等价成给定一张无向图判断能否用两种颜色给所有顶点染色使得任意一条边的两个端点颜色不同。这正是二分图的判定问题。这里有个很关键的认知转换题目表面在问“频率够不够”实际上是在问“能不能二染色”。两个频率够不够用不取决于站点总数而取决于冲突关系组成的图结构。十个站点如果排列成一条链或者一个偶环两个频率绰绰有余三个站点如果两两干扰形成一个三角形就算只有三个站两个频率也无论如何分不开。初学者最容易在这里走偏——想着用什么贪心策略、按顺序安排频率、甚至是统计每个站的干扰数量。这些方向都不是考点。题目要的就是一个干净利落的二分图判定至于为什么要用两种颜色而不是三种是因为题面固定死了频率数。把频率数改成三种问题就变成三色判定那又是另一道完全不同、难度高得多的题了。1.2 样例手推与一个常见误区拿一个最简单的冲突三角形来推站点A干扰BB干扰CC干扰A。先给A涂频率1B和A干扰所以B只能涂频率2C和B干扰所以C必须涂频率1但C和A也干扰而A恰好是频率1冲突当场暴露。这个矛盾不是代码Bug而是数学上必然的。再看偶环四个站排成环1干扰22干扰33干扰44干扰1。给1涂频率12涂频率23涂频率14涂频率2发现首尾的1和4分别是1和2不冲突成功。推这两个例子的价值在于理解奇环与偶环的本质区别。环的长度是奇数时从某个点出发按“1、2、1、2”交替染色绕一圈回到起点时颜色自己就出问题了环的长度是偶数时交替染色的最后一对正好能错开。判二分图的核心本质上就是检测图里是否存在奇环。常见误区是有人会想“那我从每个点开始BFS沿途记录层数奇偶行不行”思路接近但如果没有意识到需要把整张图的每个连通分量都跑一遍只从1号点出发遇到不连通的图就会漏判。这个坑后面专门讲。2. 建图细节与输入输出里最容易踩的坑2.1 节点编号、边数上限与存储方式选择这类题目的输入通常是第一行给两个整数n和m表示有n个发射站和m条干扰关系接下来m行每行两个编号表示这两个站点互相干扰。大多数情况下编号是1到n所以建图时一定记得把编号减1再当下标不然数组直接开成n1倒是也能跑但容易在边界判断上出问题。存储方式的选择要提前判断。如果n的数量级到几千、几万m到几万甚至十万别用邻接矩阵。我见过很多初学者习惯性开个int g[1005][1005]数据一大就内存爆炸或者无谓超时。邻接矩阵需要n^2的空间而且遍历某个点的邻居要扫一整行白白增加时间常数。面对这类题主流方案是两种一是vector邻接表适合快速写、思路清晰二是链式前向星适合追求更低常数、更喜欢数组操作的选手。下面把三者放一起对比存储方式空间复杂度建边复杂度遍历某点邻居适用场景邻接矩阵O(n²)O(1)O(n)小数据、稠密图n ≤ 2000vector邻接表O(nm)均摊O(1)O(度数)大多数题都够用链式前向星O(nm)O(1)O(度数)大数据、多组数据、要卡常数另外一个大坑是边的方向。题目说站点之间互相干扰这是无向关系所以建边时必须双向建给一条输入边(u,v)要加入u到v的边也要加入v到u的边。只建单向边的话从u能访问到v但从v就访问不到uBFS染色时会出现漏染尤其在图不连通的时候问题会被放得更大。如果输入里出现“u和u自己”这种自环也要当成一种冲突处理。一个站点当然不能自己干扰自己但一旦出现自环染成任何颜色都会导致“边的两端颜色相同”的判定成立所以当然判NO。重边无所谓多条相同的冲突关系并不会改变图的二染色属性。2.2 多组数据与初始化陷阱这个题在不少题库里是按多组数据处理的会一直读到EOF。我个人建议代码里直接用while (scanf(%d%d, n, m) 2)或者Python里read().split()一口气读进来既能处理单组也能处理多组不会有副作用。多组数据真正的杀伤力在于初始化。用链式前向星时head数组必须重置为-1cnt必须归零color必须全部清0。如果上一组数据已经跑完了head里残留着旧图的第一条边下标而这次你又只更新了部分节点遍历时就会出现从新节点链到旧节点的情况轻则判错重则越界。我早期踩过一次单组样例全部正确但一旦OJ用了多组数据封装我提交就WA。后来发现是head数组没重置第二组数据的遍历会沿着老的next指针跑到旧边上去等于二分图判定的时候凭空多出一堆“幽灵边”。从那以后只要是数组存图我每次循环开头一律先memset养成肌肉记忆。如果用的是vector邻接表多组数据时也要在每一组开头for (int i 0; i n; i) g[i].clear()。这点看起来很简单但忘记写的人并不少因为在本地跑单组测试时根本看不出问题。3. 核心算法BFS染色的完整推导与复杂度分析3.1 为什么检测奇环就能判定二分图二分图有一个等价定义无向图是二分图当且仅当它不包含奇数长度的环。这个结论是染色的基石值得展开理解一下。左半边先看必要性如果图里有奇环你可以从环上任意一点开始按“1、2、1、2”的顺序给环上的点交替染色。因为环的长度是奇数绕到最后必然有两个相邻的点被涂成同样的颜色违反规则。所以存在奇环的图绝对不可能二染色。右半边再看充分性如果图没有奇环那么从任意一个点出发做BFS每个点的层数就是确定的。把偶数层的点全部涂成频率1奇数层的点全部涂成频率2接下来需要验证会不会有冲突。冲突只有在“两个相邻点层数奇偶性相同”时才会发生如果图中存在这样一条连接两个同奇偶层点的边那么从树根到其中一个点的路径长度、到另一个点的路径长度加上这条边本身会拼出一个奇数环。这个过程逻辑链很长如果你第一次接触可能会觉得绕但能看懂这一小节BFS染色模板就再也不是死记硬背的代码而是有数学支撑的必然做法。实际编码中甚至不需要单独数层数直接用0表示未染色用1和2表示两种频率每次给邻居涂上和当前节点相反的颜色即可。3.2 为什么只从1号点发出遍历不够这是这道题最容易被误解的地方。你以为图一定是一整张连通的广域网不一定。广播网可能由多个互不相连的子网组成。比如1号构建了一个局域网4号构建了另一个它们之间根本没有干扰关系在输入里就不会出现在同一条边里。如果代码里只调用一次bfs(1)那么从1号点能染到的只有它所在的连通分量其他分量的点全部保持color0。等到输出YES前你并没有检查那些点内部是否存在冲突关系。它们内部完全可能隐藏着一个三角形而你的算法完全看不见。正确的做法是外层循环遍历所有节点凡是color为0的点都当作一个新的连通分量的起点执行一次BFS。一旦某次BFS判定失败整体输出NO并直接结束。这个逻辑类似于找连通分量只不过每个连通分量内部多了一组染色约束。3.3 BFS和DFS怎么选从算法正确性上说BFS和DFS都能完成二分图判定差别只是访问顺序。但在OJ环境里我推荐优先用BFS或者手动栈的方式。原因之一是递归DFS在链特别长的图上会爆栈。想想一条一万个点串起来的“蛇形图”递归深度直奔上万层默认栈很可能顶不住。原因之二是BFS染色时你天然可以按层次理解问题调试的时候打印每个点的层次和颜色逻辑上更直观。如果你确实想用DFS建议开一个显式栈或者用递归但在心里清楚风险。我更倾向于BFS模板因为它只需要一个队列、一个color数组几乎没有爆栈可能。3.4 复杂度分析建图阶段m条无向边需要添加2m条有向边复杂度O(m)。染色阶段每个顶点最多入队一次每条边最多被访问两次整体复杂度O(nm)。所以无论n和m多大只要在题目给的范围里这个算法理论上是线性级别的非常快。这也意味着这道题卡的不是算法本身而是你能不能把边界情况处理干净。4. 完整的AC代码与逐段注释4.1 C版——链式前向星加队列染色#include cstdio #include cstring #include queue using namespace std; const int MAXN 10005; const int MAXM 100005; struct Edge { int to, next; } edges[MAXM * 2]; int head[MAXN], cnt; int color[MAXN]; void addEdge(int u, int v) { edges[cnt].to v; edges[cnt].next head[u]; head[u] cnt; } bool bfs(int start) { queueint q; q.push(start); color[start] 1; while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i edges[i].next) { int v edges[i].to; if (color[v] 0) { color[v] 3 - color[u]; q.push(v); } else if (color[v] color[u]) { return false; } } } return true; } int main() { int n, m; while (scanf(%d%d, n, m) 2) { memset(head, -1, sizeof(head)); memset(color, 0, sizeof(color)); cnt 0; for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); addEdge(u - 1, v - 1); addEdge(v - 1, u - 1); } bool ok true; for (int i 0; i n; i) { if (color[i] 0) { if (!bfs(i)) { ok false; break; } } } printf(ok ? YES\n : NO\n); } return 0; }代码里有三个细节值得说。第一color[v] 3 - color[u]是一个很巧妙的写法。color只有1和2两种取值如果用当前节点的颜色是1那么3减1等于2如果当前是23减2等于1。这一段代码就完成了“涂相反颜色”的操作比写if判断更简洁。第二边数组开的是MAXM * 2因为无向边要存两次。如果你只开了MAXM大小一旦输入达到上限数组越界问题会让你莫名其妙地WA甚至RE而且很难排查。第三多层循环遇到bfs失败时我用break跳出再用一个ok变量控制输出。比直接return提前结束更容易理解也方便你在后面加调试输出。4.2 Python版与性能取舍from collections import deque import sys def solve(): data sys.stdin.buffer.read().split() it iter(data) out [] while True: try: n int(next(it)) m int(next(it)) except StopIteration: break g [[] for _ in range(n)] for _ in range(m): u int(next(it)) - 1 v int(next(it)) - 1 g[u].append(v) g[v].append(u) color [0] * n def bfs(start): color[start] 1 q deque([start]) while q: u q.popleft() for v in g[u]: if color[v] 0: color[v] 3 - color[u] q.append(v) elif color[v] color[u]: return False return True ok True for i in range(n): if color[i] 0: if not bfs(i): ok False break out.append(YES if ok else NO) sys.stdout.write(\n.join(out)) solve()Python版整体更贴近人的思考直觉但要注意两个地方。一是输入加速。如果m很大直接用input().split()逐行读会在IO上浪费大量时间。sys.stdin.buffer.read().split()一次性读完所有内容再按迭代器逐个数取用这是刷题Python党最通用的做法。二是bfs函数定义在while循环内部这样每组数据都能重新持有当前color列表的引用不需要额外传参也不担心闭包污染。如果你把bfs定义在外层color就得作为参数传进传出代码会变丑。这道题n不大时Python跑起来毫无压力但如果n到了10万级别Python的邻接表加BF S也能过只是常数偏大。真被卡超时的时候可以试试用list当栈做DFS访问顺序虽然不同但省去了deque的开销。5. 调试与自测模板5.1 我用来快速自测的几组数据本地写题别急着直接提交。先把下面这几组测试数据走一遍基本能覆盖绝大多数边界问题。2 0两个站没有任何干扰YES。3 1 1 2只有一条边连到第三个孤立点上YES。3 3 1 2 2 3 1 3这是个三角形包含奇环NO。4 4 1 2 2 3 3 4 4 1四人冲突环四环是偶环YES。6 4 1 2 2 3 4 5 5 6两组互不连通的路径路径不影响二染色YES。5 4 1 2 2 3 3 1 4 5一个三角形加一条孤立边图形整体不连通但三角形本身已经无解NO。1 1 1 1自环NO。部分题目数据里不会有这种输入但有备无患。用这几组数据测一遍如果全部符合预期那你的核心逻辑基本没有大错。剩下的问题多半出现在格式或题目细节上。5.2 提交WA之后按这四步排查第一步查初始化。快速扫一眼建图数组和color数组有没有在每组数据开头重置。尤其用C风格数组时这是WA第一大来源。第二步查连通分量。确认外层有没有遍历所有节点。只从1号点开始BFS在所有数据都弱连通时能过一旦数据里包含彼此孤立的多个子网就会漏判。哪怕你本地测试碰巧没碰到这种数据OJ里也一定有。第三步查自环和重边。自环必然导致NO。重边不影响判定结果但如果你的建图代码对重边有特殊处理而处理错了也会出问题。正常的邻接表存重边完全没问题不需要去重。第四步查输出格式。是要求YES/NO还是Yes/No这个在不同题库可能不一样。大小写错了裁判可不会留情直接判WA。按照这个顺序排查绝大多数问题都能定位。6. 同源问题的迁移染色模型还能解决什么6.1 一批“分组冲突”类题目都可以套染色这道无线广播题练完之后你会发现一类长得不同、本质完全一样的题有一堆对象某些对象不能放在同一组里问能不能分成两组。比如把犯人分到两个监狱要求有怨仇的两个人不能被分到同一个监狱把宠物分成两组有些宠物不能放在同一个笼子里把课程分配到两个时间段有些课程因为学生重叠不能排在同一时段。这些都是同一个模型。题面换了核心还是二分图判定。拿到这种题你的第一反应应该是把对象变成点把“不能同组”变成边然后跑BFS染色。判定成功分组方案也顺手拿出来了——color为1的一组color为2的一组。这就比单纯输出YES/NO更进一步可以直接从染色结果构造答案。6.2 用扩展域并查集也能解决二分图判定不只有染色一条路。如果你不想建图或者点的数量特别大而边比较稀疏可以用扩展域并查集。扩展域并查集的做法是把每个点i拆成两个域i表示i在第一组in表示i在第二组。对于一条冲突边(u,v)做两次合并把u和vn合并再把un和v合并。合并在并查集里的含义就是“它们必须同时成立或者同时不成立”。如果在合并之前发现find(u)等于find(v)说明u和v已经被安排进了同一组而它们本来应该是冲突的那就可以直接判定无解。这种做法的优点是省去了建图时间和内存输入一条处理一条。缺点是它只告诉你成不成不直接给你一组具体的染色结果。不过在大多数判判定类的题目里我们只需要YES/NO这个解法完全够用。6.3 更远的远方是K着色问题二分图判定本质上是“二着色判定”。如果把频率数从2改成k题目就变成一般图k着色问题。二分图判定有线性算法一般图的三色判定却是NPC问题这不是代码写得好不好能解决的而是问题本身的计算复杂度发生了质变。知道这件事之后你在面对“能不能用m种颜色给图染色”的题目时就能马上分辨它属于可解的二分图判定还是不可解的硬核NPC问题。如果发现题目是后者合理的第一反应不是去写暴力搜索而是去看题目是否加了额外约束比如图是不是树、是不是平面图、k是不是很小可以状态压缩。回到无线广播这道题它没有那么多花哨的变化就是一次干净利落的二分图判定。但恰恰是这样一道基础题把建图、遍历、非连通图处理、边初始化这些底层素养全串起来了。我个人刷这类题的心得是不要背模板而是把“为什么有奇环就无解”“为什么非连通图要扫全”“为什么无向边要建两次”这些为什么讲清楚之后再遇到任何带冲突关系的题目你都比别人少踩一大半坑。