企业官网建设流程全解析

做了这么多年 OJ，能在第一眼就让人产生"这题有点东西"感觉的图论题不多，"无线广播（Broadcast）"算一个。光看名字，容易以为是通信专业的网络规划题，什么信号覆盖、信道分配、广播站点，读题像是在看工程文档。可实际上，这是一道纯粹的图论问题：给你一张无向图，问能不能用两种颜色给所有顶点染色，使每条边两端的颜色不同。用行话讲，就是判断这张图是不是二分图。

我第一次见到这道题，是在某高校 OJ 的图论专题里。当时刚学完 BFS，脑子一热就想用最短路硬做，交上去一排 WA 把我打醒了。后来冷静下来，把题面翻译成图模型，十分钟就过了。这篇文章我把完整的建模思路、算法流程、参考代码和一些容易踩的坑都整理出来，适合刚学完图遍历、想在真题里练手的同学，也适合准备面试手撕算法、想快速复习二分图判定的朋友。

1. 先把广播场景翻译成图论模型

1.1 从题面到顶点和边的映射

先把题面场景还原一下。广播网络里有若干节点（通常是发射塔或基站），节点之间只要距离足够近，就能直接通信，形成一条通路。现在要给每个节点分配一个广播通道，规则是：任何两个存在直接通路的节点，它们的通道必须不一样。题目只提供两种通道，问有没有可能做到。

这几乎就是为图论量身定做的场景：

• 节点对应图的顶点；
• 节点之间的直接通路对应无向边；
• 两种通道对应两种颜色；
• "相邻节点通道必须不同"对应"相邻顶点颜色必须不同"。

做完这层映射，问题的真面目就露出来了：给定一张无向图，能否用两种颜色给所有顶点合法染色，使得任意一条边的两个端点颜色不同？这就是标准的二分图判定问题，也叫二染色问题。

1.2 为什么"两种通道"等价于"二染色"

把话说得更细一点。二染色要求把顶点分成两个集合，集合内部的点之间可以有任意关系，但所有边都必须横跨两个集合，不允许出现集合内部的边。一旦出现内部边，这条边两端的颜色就必然相同，直接违反规则。

反过来，只要一张图能二染色，就等价于存在一个顶点划分，把图分成左右两组，所有边都在两组之间。这个性质和广播问题里的约束是一一对应的：颜色 1 的节点用通道 A，颜色 2 的节点用通道 B，相邻的两个节点必然落在不同集合，通道也就必然不同。

这里有个判断捷径：一张图能二染色，当且仅当它不含长度为奇数的环。三角形的三个顶点两两相连，环长度为 3，是奇数，所以三角形永远无法用两种颜色合法染色，这就是"无线广播"题里输出 NO 的核心原因。相反，四边形（4 环）就能染，A 染 1、B 染 2、C 染 1、D 染 2，首尾检查一遍全部合法。

提示：学有余力的话可以自己证明"奇数环是二分图的唯一障碍"。思路是：从环上任一点出发沿环走一圈，每走一条边颜色就切换一次，走完一个长度为奇数的环回到起点时，颜色恰好被切换了奇数次，起点自己的颜色和自己冲突。

2. 核心算法：BFS 染色法完整拆解

2.1 染色流程的通俗版和正式版

通俗地说，这题就是给地图涂色，规则是"接壤区域必须异色"。手动操作流程是：随便找一块还没涂色的区域，涂成红色；然后所有和它接壤的区域涂蓝色；所有和蓝色接壤的区域再涂红色，一路铺开，直到这块连通区域全部涂完。铺的过程中发现某个区域已经被涂过色，而且颜色和当前要求的颜色冲突，那么整张图宣告失败。

正式化的算法步骤是这样的：

1. 用 color 数组记录每个顶点的颜色，0 表示未染色，1 和 2 表示两种颜色；
2. 遍历所有顶点，凡是遇到 color 为 0 的顶点，就把它作为起点启动一次 BFS；
3. BFS 中，起点染成 1；每次从队列取出顶点 u，遍历它的所有邻居 v；
4. 如果 v 未染色，染成3 - color[u]，也就是和 u 相反的颜色，然后入队；
5. 如果 v 已经染色，检查它和 u 的颜色是否相同，相同则直接返回失败；
6. 所有起点都 BFS 完且没有冲突，整体可行。

3 - color[u]是一个很实用的小技巧。color 取值只有 1 和 2，当 u 是 1 时结果是 2，u 是 2 时结果是 1，一行代码完成颜色切换，不用写 if-else。这个写法在很多染色类题目里都能复用。

2.2 为什么 BFS 染色不会漏解也不会假阳性

需要解释一个很多人会问的问题：为什么 BFS 染一遍就能下结论，不会漏掉某些情况？

关键在于，图里的关系是沿着边传递的。一旦起点颜色确定，和它直接相连的顶点颜色就被强制确定，这些顶点又继续强制它们的邻居……整个过程只有一条逻辑链。BFS 从起点开始，一层一层把整个连通分量扫完，每个被访问的顶点都只可能有一种"被强制决定"的颜色。如果颜色没有冲突，说明这个连通分量确实存在一种一致的颜色安排；如果出现冲突，说明无论怎么调整起点颜色都无法避免，因为起点颜色翻转后，整个连通分量的颜色只会整体互换，冲突点依然冲突。

另一个常见误区是对非连通图处理不到位。图可能由多个互不相连的连通分量组成，比如顶点 1、2 之间有边，顶点 3、4 之间有边，但两组之间没有任何通路。如果只从 1 号顶点做一次 BFS，顶点 3、4 根本访问不到，程序会漏判。所以算法第 2 步的外层循环是这个题的关键，每个未染色顶点都要当作起点跑一遍。每个连通分量的起点颜色互相独立，是选 1 还是选 2 不影响整体可行性。

2.3 建图方式和复杂度分析

建图用邻接表。顶点数通常到十万级别甚至更高，邻接矩阵的话空间是顶点数的平方，直接爆炸，所以必须用vector<int> adj[MAXN]这种动态数组。每读入一条边 a-b，就在 a 的邻接表里加入 b，在 b 的邻接表里加入 a，因为这是无向图。

时间上，每个顶点入队一次，每条边作为"邻居"被检查两次（两个方向各一次），总复杂度 O(N + M)。这个量级在绝大多数 OJ 上都是秒过，不需要任何额外的剪枝优化。需要警惕的是递归 DFS 版本——如果图是一条超长链，比如十万个节点串成一串，递归深度就是十万，超出默认栈空间会段错误。所以除非评测环境明确提供了足够的栈空间，否则首选 BFS。

3. 实操记录：从读题到 AC 的完整链路

3.1 一份实测可用的参考实现

下面这份 C++ 代码是完整可提交的，我在不同学校的评测环境里都跑过，没有依赖特殊编译选项，直接交就行：

#include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int MAXN = 100005; vector<int> adj[MAXN]; int color[MAXN]; bool bfs(int s) { queue<int> q; color[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { 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 && (n || m)) { for (int i = 1; i <= n; ++i) adj[i].clear(); memset(color, 0, sizeof(color)); for (int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); } bool ok = true; for (int i = 1; i <= n && ok; ++i) { if (color[i] == 0) { if (!bfs(i)) ok = false; } } puts(ok ? "YES" : "NO"); } return 0; }

几个值得注意的实现细节：

• while (scanf("%d %d", &n, &m) == 2 && (n || m))是标准的读多组数据写法，以"n 和 m 同时为 0"作为结束标记。如果题面只给单组数据，把循环改成单次即可；
• 每组数据开始前必须先adj[i].clear()和memset(color, 0, sizeof(color))，否则上一组数据残留的边和颜色会污染下一组；
• 主循环里一旦 bfs 返回 false，就用&& ok短路退出，省得继续做无用功；
• 如果题目要求输出染色方案（而不是仅输出 YES/NO），只需要把最后的输出改成打印color[1]到color[n]，或者遇到冲突时打印 -1。

3.2 边界用例自测清单

提交前建议先跑一遍这些用例，能覆盖这个题 90% 的坑：

自环和重边的处理要看题面约定。多数题目默认没有自环和重边，但如果没写明，最好让代码对这两种情况保持鲁棒：自环用染色逻辑天然判为 NO；重边退化为普通边，不影响结果。

3.3 一次典型调试复盘

说说我自己那次调试经历。第一版我用递归 DFS，小样例全过，一提交就段错误。排查后发现测试数据里构造了一条很长很长的链，递归深度超过系统栈上限，直接崩了。改成迭代 BFS 之后，段错误消失，但依然 WA。后来和同机房的同学一起对着代码逐行查，才发现问题出在主循环：我当时只在 1 号顶点上调用了一次bfs(1)，没有遍历其他连通分量。两个问题都修掉之后，这道题才真正过了。

那次之后我总结了一条经验：图论题的样例通常特别善良，单连通、小规模、编号从 1 开始，但后台数据专门挑不连通、超长链、极端编号这些场景下手。提交前先自己在草稿纸上把"单点、无连通、长链、奇环"四个用例跑一遍，能省下至少两三次无谓的提交。

4. 常见问题与排查心得

4.1 高频报错速查表

把新手常见的错误整理成一张表，方便快速对号入座：

最后一行是重灾区。无向图的邻接表如果只在adj[a].push_back(b)而忘了adj[b].push_back(a)，图就变成了有向图，很多本该冲突的边不会被反向检查到，于是所有答案都是 YES。遇到"全 YES"这种诡异现象，第一个要怀疑的就是建图少了反向边。

4.2 隐藏很深的三个细节

第一个细节是节点编号起点。有的题目顶点从 1 开始，有的从 0 开始，数组开多一个位置没关系，但循环边界必须跟着题面走。如果题面从 0 开始，外层循环就写成for (int i = 0; i < n; ++i)，建图时数组下标也和顶点编号对齐。

第二个细节是输出格式。有些题要求YES，有的要求Yes，还有的只要Y或N。不要自己凭感觉敲，把样例输出的格式原样复制到代码里最稳妥。这个细节和算法无关，但就是能让人多交几发 WA。

第三个细节是内存清理。memset(color, 0, sizeof(color))只对 color 数组有效，邻接表必须逐个clear。如果只做了前者忘了后者，上一组数据的边会残留在 vector 里，导致这组数据多出一堆假边，结果全错。写多组输入的题目时，这两步最好放在一起做。

5. 题外话：二分图判定的工程价值

5.1 真实场景里哪里在用

刷题的时候容易觉得"二分图判定"是个纯考试概念，其实不是。无线网络频点规划就是最直观的例子：移动通信网络里，相邻基站如果使用同一个频点，覆盖重叠区的信号会互相干扰。工程上做小区的频点分配，第一步就是检查"邻区关系图"能不能二染色，能染就用两个频点把干扰问题彻底绕开，不能染就得引入第三个频点或调整功率。你在这道 OJ 题里写的 BFS 染色，放大到几千个小区、几万条邻区关系的规模上，依然是核心算法骨架。

类似的场景还有：任务调度的冲突消解（两个任务不能同时占用同一资源时，判断能否分成两个时间段）；排课问题（两个班不能共用同一教室时，判断能否分成两天）；甚至社交网络里"好友关系图"的一些社区发现算法，也把二分图判定当作基础组件。算法题和工程实践之间的距离，往往比想象中近得多。

5.2 学完这道题还能往哪个方向走

这道题本身是二分图判定的入门款。沿着这条线往下，可以解锁一串相关的经典问题：

• 带权并查集版本：同样是判断"两种关系"的冲突，但用并查集维护相对关系，复杂度相近，写法完全不同；
• 二分图最大匹配：判定完之后，如果想求"最多能配多少对"，就进入匈牙利算法的领域；
• 奇环与图的二分性：判定奇数环的存在性、统计奇环数量等延伸题，也大多从染色法出发；
• 三染色与图着色推广：从两种颜色推广到 k 种颜色，问题的难度会急剧上升（k 染色判定是著名的 NP 困难问题），这也是为什么"两种颜色"这个条件如此重要。

我个人建议的顺序是：先把 BFS 染色写到闭眼能默写的程度，再去看带权并查集的做法，两相对比能帮你把"关系传递"想透彻。匈牙利算法可以等接触二分图匹配题时再配着学，不必一次铺太开。

最后再分享一点个人体会。这类披着应用场景外衣的基础图论题，最忌讳的就是被题面牵着鼻子走。我现在读题有个习惯：读完先不动手，在草稿纸上把"实体→顶点、关系→边、约束→颜色规则"的映射写出来，再决定用什么算法。"无线广播"这道题，灵魂就在"两种通道"和"相邻必须不同"这两个条件里，翻译成图论语言之后，剩下的就是一遍 BFS 的事。把这个读题习惯练成肌肉记忆，以后再遇到什么"社交距离""航班冲突""染色问题"，一眼就能看到本质。