做 UVa 12860 Galaxy Collision 时我最开始其实想错了方向——看到“碰撞”两个字就直奔最大匹配去了敲到一半才发现题目真正考的是一套非常经典的图论建模把一个暧昧的故事转成无向图再用二分图染色统计每个连通分量。如果你也卡在这题的“二分”从哪来、“统计”到底在统计什么这些问题上这篇文章应该能帮你把整条链路理顺。这个问题通常被归类为二分图染色入门题适合刚学完 DFS/BFS、开始接触图论模型的读者。它的难点并不在算法本身而在于能不能把背景描述翻译成正确的图结构以及理解为什么每个连通分量的贡献可以独立累加。我会从题目翻译、染色原理、关键实现、实际提交时的坑到它和最大匹配问题的边界一层层展开。1. 题目到底想让我们输出什么拿到题以后不要急着写代码先做一件事把题面里的故事性句子全部划掉只留下数据关系。UVa 12860 的“星系碰撞”背景剥开以后就是下面这张图。1.1 碰撞关系等价于一条无向边题面里会给 N 个星系和 M 对碰撞关系。把每个星系看成一个点每一对会发生碰撞的星系之间连一条无向边那么整个宇宙就是一个由点和碰撞关系构成的图。这里有一个容易理解偏的点边代表“碰撞关系”而不是“已经撞上了”。也就是说两个点之间存在一条边意味着这两个星系如果被分配到同一边就会发生碰撞如果被分到不同边则不会碰撞。这个“分到两边”的动作就是我们要求的决策。题目里还隐含了一个条件一个星系不能同时处于两个“阵营”。放到图论里这就是对每个点只染一种颜色。于是问题就变得非常干净——我要把所有点染成两种颜色让每条边的两个端点颜色不同同时让某个颜色对应的星系数量最小。1.2 输出“损失最小值”而不是“碰撞次数”很多同学拿到这题以后会困惑既然要最小化碰撞那我直接数一数有多少条边两端颜色相同不就行了吗不对。这道题要求输出的是“受到影响的星系数量”也就是落在危险一侧的点的个数而不是冲突边数。你可以这样理解每个星系最终要么被分到安全侧要么被分到危险侧。一条边两端必须不在同一侧否则整条边上的星系都会出问题。我们的目标是最小化危险侧的星系数量。这样目标函数就变成了在图的所有合法“二染色”方案中找一个方案使其中一种颜色的总数尽可能小。而一个图要想存在合法二染色方案前提条件就是它必须是二分图。题目给出的数据一般都会保证这一点否则问题性质会完全不同后面我会详细解释为什么。所以解题的第一步是把输入的 M 条边全部建进邻接表然后对每个连通分量做二分图染色统计两种颜色各自有多少个点。2. 二分图染色为什么是这个题的主角二分图这个概念如果第一次接触会觉得有点抽象。其实它就是“可以用两种颜色给所有点染色使所有边的两个端点颜色不同”的图。说得更直观一点你可以把这个图的所有点分成两个集合 A 和 B让所有边都跨在 A 和 B 之间不会有一条边两端全在 A 或全在 B 里。2.1 一维颜色无法满足奇环为什么不是所有图都能二染色关键在于奇环。一个三角形三个点两两相连你试着给三个点交替染成 0、1、0最后第三个点和第一个点之间颜色相同矛盾就出现了。实际上任何长度为奇数的环都会导致类似矛盾。反过来没有奇环的图一定是二分图。这个结论是二分图理论的基础做题不需要每次都证明但可以嘴上复述一遍从任意一个点出发用 0 和 1 交替染色如果出现矛盾就说明存在一条长度为奇数的闭合路径如果没有矛盾染色就成功完成。在 UVa 12860 的题目背景下如果整张图是二分图就意味着存在一种合法的“分侧方案”可以保证每条边上的两个星系都是异侧关系。如果我们再进一步要求“危险侧点数最少”那就需要在染色结果上做文章。2.2 证明它的过程其实是在写判段我自己的一个体会是二分图染色过程和“判断一个图是否为二分图”几乎是同一件事。你不需要额外写一个函数去“验证二分性”因为染色过程中如果遇到颜色冲突你自然就知道它不是二分图了。实现思路是给每个点初始化颜色为 -1表示未染色。遍历所有点如果发现未染色就从它开始做一次 BFS/DFS。起点染成颜色 0邻居颜色必须为 1邻居的邻居再染成 0依此类推。如果某个点已经被染色但要求的颜色和它实际颜色不一致说明存在矛盾。我把这个逻辑写成了一个处理单个连通分量的函数在后面第 4 节的代码中会完整给出。这里想强调的是判断二分性和统计两种颜色的数量可以放在同一次遍历里完成不需要扫两遍图。3. 同分量能整体翻色不同分量才可独立累加假设我们已经成功把图染成了 0/1 两种颜色接下来要做的是把每个连通分量的贡献合并成最终答案。这一步看着简单但很多人会在这里踩坑直接对所有点的颜色数量做全局统计然后取 min(cnt0, cnt1)。这样做的错误在于不同连通分量之间的“颜色 0/1”并不是可以随意互换的。你需要意识到二分图染色得到的颜色标签在每个连通分量内部是固定的但不同分量之间没有约束关系所以每个分量都可以整体翻转颜色。3.1 每个分量贡献 min(cnt0, cnt1)来看一个连通分量内部的逻辑。假设这个分量染完以后颜色 0 有 a 个点颜色 1 有 b 个点。因为分量内部没有跨分量的边所以我可以把这个分量的所有 0 和 1 整体对调对整张图的合法性没有任何影响。如果题目要求“危险侧尽量少”那么这个分量里被分到危险侧的星系数量要么是 a要么是 b取决于我把哪一种颜色定义为危险侧。显然我应该选择较小的那一个所以该分量的贡献就是 min(a, b)。需要注意的是这种翻色只能对整个连通分量做不能对单个点做。如果你单独把某个点从 0 改成 1但它的邻居还是 1那这条边就变成同色边方案立刻非法。3.2 用一个能跑通的小图演算我自己验证的时候用了一个 4 个点、两条边的简单图来模拟点 1 和点 2 相连点 3 和点 4 相连。这个图有两个连通分量每个分量都是一条单独的边。对第一条边染色结果为 (0, 1)颜色计数是 a1, b1贡献 min(1,1)1。对第二条边同样是 a1, b1贡献又是 1。最终答案就是 2。这个答案很符合直觉每条边的两端必须分到不同侧所以每条边至少要牺牲一个点。有的朋友可能会问那我让每条边的两端一个安全一个危险是不是所有边都满足确实是而且每个分量只能牺牲一个点再少就不可能了。再看另一个例子一条长度为 3 的路径有 4 个点。染色后颜色 0 有 2 个点颜色 1 有 2 个点贡献是 min(2,2)2。注意路径长度为 3表示有 3 条边但只牺牲 2 个点就够了这比“牺牲边数”要少。原因是一个点可以同时充当两条边的“危险端点”例如路径中间的某个颜色 1 点可以同时和左右两个颜色 0 点相连。4. 核心代码实现用BFS代替DFS免栈溢出下面给出我最终提交版本的简化代码。这里用 BFS 队列做染色而没有用递归 DFS主要是有一次在另一个大数据题里被递归栈溢出教训过从那以后涉及大规模图染色我都默认用迭代写法。4.1 染色遍历如何避免重复入队#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; int color[MAXN]; long long solveOneComponent(int start) { queueint q; q.push(start); color[start] 0; long long cnt[2] {0, 0}; cnt[0] 1; while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (color[v] -1) { color[v] color[u] ^ 1; cnt[color[v]]; q.push(v); } else if (color[v] color[u]) { // 说明这个连通分量不是二分图 // 按题目保证大部分输入不会走到这里 return -1; } } } return min(cnt[0], cnt[1]); } int main() { int n, m; int caseNo 1; while (scanf(%d%d, n, m) 2) { if (n 0 m 0) break; for (int i 0; i n; i) { g[i].clear(); color[i] -1; } for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); // 如果输入给的是 1-index 点编号就转成 0-index --u; --v; g[u].push_back(v); g[v].push_back(u); } long long ans 0; bool bad false; for (int i 0; i n; i) { if (color[i] -1) { long long cur solveOneComponent(i); if (cur -1) { bad true; break; } ans cur; } } if (bad) { // 按题目语义处理非二分情况通常不出现 printf(Case %d: 0\n, caseNo); } else { printf(Case %d: %lld\n, caseNo, ans); } } return 0; }这套代码的核心逻辑就三件事每个点只入队一次、每次决定邻居颜色用color[u] ^ 1、计数器在染色时同步更新。只要这三点不出错整个流程就不会有重复统计的问题。4.2 多测试数据下初始化与输出的陷阱这种题大多是多测试用例最烦人的不是算法本身而是上一次测试的数据残留。如果你用静态数组存储边清空邻接表时最容易出事。我自己的习惯是直接用vectorint g[MAXN]每轮测试开始时逐个clear()并且把color数组全部重置为 -1。还有一个细节输出格式里往往要求Case 编号:很多人会把编号从 1 开始但写完循环后忘记在末尾导致所有测试数据都输出Case 1。这个问题我提交的时候至少犯过两次最好在写printf前就先在草稿纸上确认一下编号变量的更新位置。输入结束条件也要仔细看题面。有的版本用n 0 m 0结束有的直接读到 EOF。我上面的代码用的是while (scanf(...) 2)然后单独判断n0m0兼容了两种情况。5. 提交时最容易被卡住的几个细节这部分不是算法理论但往往是真正影响 AC 的地方。我把实际提交过程中遇到的几个问题整理出来能帮你少走不少弯路。5.1 邻接表初始化方式导致的 WA有一次我图省事只把color数组重置了忘了清邻接表。因为是多组数据第一组数据的边全残留在g里面第二组数据跑的时候染色过程中访问到了上一组的节点导致计数器完全错乱输出直接崩掉。这个问题的根因是静态数组的生命周期是整个程序而不是单个用例。所以每轮测试用例开始必须把之前用到的所有数据结构重置。更稳妥的做法是用vectorvectorint并在每一轮根据 n 动态调整大小比如vectorvectorint g; g.assign(n, vectorint());这样至少能避免“上一组大图覆盖了下一组小图”带来的越界风险。5.2 非二分图数据出现后怎么处理如果某个连通分量在染色过程中发生了颜色冲突说明这个分量不是二分图。正常情况下标准数据不会给你这种输入因为一旦出现这个问题就从图染色题退化成 NP-hard 问题了。但作为工程实现我还是建议你写一个bad标志位检测到非二分图后不要继续把计数结果累加进答案。至于冲突分量应该如何计算要回到题面去看是否有特殊约定。大多数训练题目的解法都是“二分图染色 统计即可”所以如果你真碰到了非二分数据且题目没有额外说明先回头检查一下自己的建图是不是错了。5.3 单点分量和孤立点要不要算进答案如果一个点没有任何边它单独构成一个连通分量。从某个点开始 BFS起点染成颜色 0cnt[0] 1cnt[1] 0贡献为min(1, 0) 0。也就是说孤立点不影响答案这其实也符合直觉它不会和任何星系碰撞自然不应该被算进危险侧。但要注意如果你的实现里默认把孤立点染成颜色 0而另一个连通分量的起点也恰好染成颜色 0这不代表它们之间有任何关联。每个连通分量都是从自己的起点重新染色颜色编号是相互独立的。很多刚入门的朋友看到两个分量的颜色都是 0就以为它们必须在同一侧这是一个常见的误解。跨分量关系完全不存在所以全局答案才能用累加。6. 别和另一类“碰撞计数”题目混为一谈“Galaxy Collision”这个名字确实容易让人联想到匹配问题因为“碰撞”这个词经常被用来描述一对一的匹配关系。比如有一些题目会问给定若干碰撞关系最多能产生多少次互不干扰的碰撞这种问题本质上是在求图的最大匹配和 UVa 12860 的解法完全不同。6.1 最大匹配与染色统计的适用范围对比最大匹配关心的是“边”而这道题关心的是“点”。匹配想让尽量多的边互不共享端点染色统计想让每种颜色下的点数尽量平衡或不平衡。它们虽然都活跃在二分图领域但目标和证明手段差异很大。问题类型核心目标典型解法复杂度二分图染色统计分配点侧别最小化单侧点数DFS/BFS 染色 连通分量计数O(N M)二分图最大匹配找到最多的互不共享端点边集匈牙利算法 / Hopcroft-KarpO(VE) 或 O(E√V)一般图最大匹配在非二分图上求最大匹配带花树算法较复杂如果你每次看到“碰撞”都默认上匹配遇到染色题就会既超时又算错答案。我的建议是拿到题以后先确认两件事输出的是点数还是边数约束条件是让每条边两端异侧还是让两条边互不相交把这两点想清楚题目的解法归属基本就确定了。6.2 从银河碰撞到更大一类建模题的迁移价值做 UVa 12860 最大的收获其实是建立一种“把约束条件翻译成染色规则”的直觉。很多看似复杂的题目最后都能归结为“能不能把图分成两个集合使每条边横跨两个集合”。比如社交网络中的“好友分组”问题要把所有人分成两组任何一组内不能有敌对关系。这就是标准的二分图判定和染色问题。再比如排课表问题课程和学生之间有关系同一时间不能冲突本质上也可以建模成二部图加染色约束。尤其建议读者在学完本题后去手推一遍“为什么每个连通分量取 min 而不是取 max”。这个推导看似简单但它是很多二分图综合题的基础。等你真的理解了“翻转某个连通分量的全部颜色不会影响其他分量”这个性质以后再遇到“让某侧尽量大/尽量小”的变体就能很快想到从每个分量的 a、b 计数入手而不是乱猜结论。
