月赛里看到 P15445“永远在一起”这个题名时我第一反应是“字符串匹配不是吧又是后缀自动机”结果点进去仔细读题才发现它本质上就是一道并查集而且难度很符合月赛T2的定位想通之前觉得绕想通之后代码量还不到一百行。题目本身没有出什么幺蛾子关键是要把“永远在一起”这个浪漫表达翻译成“若干个元素的相等关系必须同时成立”。如果你也在赛后查题解或者正卡在这个题的某个样例上这篇内容可以帮你把整个思路理顺。我会从题意拆解、算法选型、常见优化、完整实现和踩坑记录五个角度来讲代码部分直接用 C所有讲解都围绕月赛场景尽量贴近真实比赛时的心态。1. 题目到底在说什么拆开“永远在一起”这五个字1.1 趁热还原一遍我在赛场上读到的题意原题面经过正常的数据封装之后大概是下面这个模式现在有若干“个体”它们之间的某些关系是固定的有的说两个个体必须“永远在一起”相当于要求这两个个体在最终方案里被划分到同一个等价类里还有的说两个个体“必须永远不在一起”相当于要求它们不能处于同一个等价类。问题是给定的所有条件能不能同时成立。为了不剧透完整题面我这里把输入格式抽象一下方便后面讲代码时统一使用。第一行两个整数n和mn是个体编号范围的上限m是约束条数。接下来m行每行三个整数a b c。c 1表示a和b必须在一起相等。c 0表示a和b必须不在一起不相等。如果所有约束可以同时满足输出YES否则输出NO。我当时看到这个题面之后做的第一件事不是想算法而是先画了两个小样例。4 3 1 2 1 2 3 1 1 3 0这个样例显然矛盾1 和 2 在一起2 和 3 在一起根据等价的传递性1 和 3 也一定在一起但第三条又要求 1 和 3 必须分开所以答案是NO。反过来把第三条改成1 2 0也一样矛盾。这个小小的推演直接暴露了题目的核心考点相等关系具有传递性而“不在一起”不是一种可以合并的关系它只会用来做最终的冲突检测。1.2 第一眼容易想歪的几个方向说实话竞赛里看到“在一起”“分隔”“永远”这种字眼很容易往图论里的连通分量、P和NP、甚至字符串循环节上去想。我一开始怀疑这道题是不是要用差分约束系统因为差分约束可以把形如x_a - x_b d的条件转化到图上跑 SPFA 判负环。但细看条件这里没有“大小关系”只有“相同”和“不同”它们不满足差分约束需要的数值差值结构所以第一秒就把差分约束排除了。还有人可能会往 2-SAT 方向想认为每个变量取两个值然后“相等”和“不等”是布尔限制。确实 2-SAT 能做但杀鸡用牛刀了。月赛T2一般不会考后缀自动机或者带权二分图它希望你能发现“相等约束只需要合并不相等约束只需要判矛盾”这个朴素模型。一旦想明白这一点代码就非常简单。1.3 相等关系的三个性质决定了并查集必定可行这里值得多花一点笔墨。为什么并查集天然适配这道题不是巧合而是因为“相等”本身是等价关系满足三个关键性质自反性任何一个个体和它自己必须在一起这个不需要额外合并。对称性a和b在一起那么b和a也在一起所以合并操作是无向的。传递性a和b在一起b和c在一起那么a和c一定在一起。这是并查集连通块合并时最宝贵的性质。“不在一起”则相反它不具备传递性。a不跟b在一起b不跟c在一起推不出a跟c怎么样。所以不能把“不在一起”也当成一种边去合并只能最后检查。整道题的算法骨架就出来了先把所有“必定在一起”的约束全部合并成若干个连通块然后逐条检查“不在一起”的约束只要发现两端已经在同一个连通块里说明矛盾。2. 算法选型与复杂度为什么是并查集而不是其他模型2.1 相等约束等价于无向图的连通块合并把每个个体看成无向图里的一个点把每条c1的约束看成一条连接两个点的无向边那“最终必须在一起”的点对其实就是在同一个连通分量里的点对。并查集干的正是这件事动态维护连通的点集支持合并两个集合、查询两个点是否在同一个集合。时间复杂度接近 O(1)配合路径压缩和按秩合并实测非常稳定。如果你把c1的边先收集起来再用 DFS/BFS 染色连通分量也能得到正确结果。但缺点是代码量变大而且需要保存邻接表。比赛里多组数据时vector的反复clear()和resize()容易写错。并查集只需要一维数组初始化也简单更适合在月赛这种限时环境里使用。2.2 “不在一起”的处理先合并后判断是唯一安全顺序这里有一个特别经典的问题能不能在输入一条c1或c0时就即时判断理论上也可以但分情况讨论会变得很繁琐。比如先输入a c0 b此时不知道未来会不会出现a和b通过中间节点合并的约束如果立刻判断它俩不在一个集合就说“暂时合法”后续合并又会把矛盾遗漏。反过来如果每来一条c1都去重查所有历史c0约束复杂度就爆炸了。所以正确的方针是离线两段式处理先把所有c1的约束全部读入并执行合并让所有等价关系完整传递把连通块固定下来。再重新扫描所有c0的约束逐一用find(a) find(b)判断是否矛盾。这个顺序的好处是当检查c0时并查集已经包含了全部“相等”信息不会因为合并顺序导致误判。你可以理解为我们在搭积木最后才检查那些“不允许连接”的孔位。2.3 复杂度分析与数据范围预判假设约束总条数是m最坏情况下每个个体编号不一样所以需要管理的不同点数最多2m。排序去重离散化的复杂度是O(m log m)并查集执行m次合并和检查路径压缩后均摊复杂度接近O(m α(2m))其中α是反阿克曼函数在合理数据范围内基本可以当成常数。因此整道题复杂度瓶颈在离散化排序而不是并查集本身。如果题目给的数据范围是n 1e9, m 2e5那O(m log m)在 C 下是稳过的。这提醒我们千万不要因为看题面里n很大就去开n1大小的数组否则连编译都会挂更别说运行内存了。3. 核心细节与优化P15445 真正的大坑都在这些地方3.1 离散化把 1e9 的编号压成 2e5 的数组下标好多第一次接触这类题的同学会问n不是给了吗为什么不直接vectorint fa(n1)因为n可以大到1e9开一个十亿长度的数组直接爆内存。竞赛环境内存通常 256MB 或 512MB一个 int 4 字节十亿个就是 4GB不可能塞进去。解决办法是离散化。但需要区分两种离散化方式第一种如果输入编号本身就是 1 到 n 的稠密排列确实可以开n1。但题目没有保证时不能这么赌。第二种只把实际出现在约束里的编号收集起来排序去重后建立映射。因为每条约束有两个端点m条约束最多只涉及2m个不同编号。之后并查集大小就取2m而不是n。我写代码时习惯把所有端点塞进vectorint nums排序后unique然后用lower_bound建映射。因为lower_bound是二分查找复杂度O(log M)配合后面的并查集操作完全没问题。如果你担心常数可以换用unordered_map但后面会讲它可能带来的新麻烦。3.2 路径压缩与按秩合并两个优化都不建议省并查集的标准优化有两个分别是路径压缩和按秩合并。路径压缩是在find过程中顺手把x直接挂到根节点下让后续查询走得更短。按秩合并是在unite时把深度小的树挂到深度大的树下面控制树高。二者合起来可以保证单次操作均摊复杂度接近反阿克曼函数这个复杂度几乎是常数。我见过有人贪省事只写路径压缩不写按秩合并在大多数数据上也能过但月赛的测试点经常不放水。当数据被构造为深度很大的链时没有按秩合并会让递归深度爆栈出现诡异的内存溢出或超时。所以完整写法一定不要省。代码里我用sz数组记录集合大小合并时让小集合挂到大集合下面一样能达到按秩合并的效果。3.3 输入输出优化月赛T2的生死线这道题的读入是n m随后是3m个整数。如果m是2e5或者更大用cin默认同步模式直接读可能要多花几百毫秒甚至一秒。在总时限只有 1s 的月赛里有时候你以为自己算法错了其实是 IO 拖了后腿。我固定会加这两句话ios::sync_with_stdio(false); cin.tie(nullptr);但注意加了之后cout和printf最好不要混用否则输出顺序会乱。如果你连这两行都不放心可以直接手写快读类似getchar()读数字。不过一般月赛题cin取消同步就够了不需要过度优化。3.4 多组数据时的清空陷阱如果矩形题面里有多组数据那每组测试都要重新初始化nums和并查集否则上一组残留的编号会让这一组的映射错乱。我常在赛后看到有人把nums.clear()写在读入循环外面结果后面lower_bound找不到值。正确做法是每组数据开始前nums.clear()读入后用局部变量DSU声明并查集这样析构时会自动释放比手动clear更安全。4. 完整实现C 代码 逐行注释4.1 整体框架分几块代码一共分为四块定义查询结构体Query存a, b, c。把输入端点压入离散化数组。实现DSU类包含find和unite。主函数里先合并所有c1再检查c0。这个结构非常清晰写完不容易乱。我直接给出完整代码这份代码在本地和在线评测都实测通过我构造的测试数据。4.2 完整代码#include bits/stdc.h using namespace std; struct Query { int a, b, c; // c1 在一起 c0 不在一起 }; class DSU { private: vectorint fa, sz; public: explicit DSU(int n) { fa.resize(n 1); sz.assign(n 1, 1); iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unite(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return; if (sz[rx] sz[ry]) swap(rx, ry); // 按大小合并 fa[ry] rx; sz[rx] sz[ry]; } bool same(int x, int y) { return find(x) find(y); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { // 支持多组数据 vectorint nums; vectorQuery qs(m); for (int i 0; i m; i) { cin qs[i].a qs[i].b qs[i].c; nums.push_back(qs[i].a); nums.push_back(qs[i].b); } sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 离散化映射 auto getId [](int x) - int { return int(lower_bound(nums.begin(), nums.end(), x) - nums.begin()) 1; }; DSU dsu(int(nums.size())); // 只开不同编号的个数 1 // 第一阶段合并所有必须在一起的约束 for (const auto q : qs) { if (q.c 1) { dsu.unite(getId(q.a), getId(q.b)); } } // 第二阶段检查所有不能在一起的约束 bool ok true; for (const auto q : qs) { if (q.c 0) { if (dsu.same(getId(q.a), getId(q.b))) { ok false; break; } } } cout (ok ? YES : NO) \n; } return 0; }4.3 用一组样例完整走一遍流程我构造一组合法的样例5 4 1 2 1 2 3 1 4 5 1 1 4 0第一步离散化数组里会有1 2 3 4 5映射分别是1 2 3 4 5。然后合并1 2、2 3、4 5得到两个连通块{1,2,3}和{4,5}。检查1 4 0时find(1) 1find(4) 4不在同一个块所以输出YES。再来一组矛盾样例可以直接复用最前面那个4 3 1 2 1 2 3 1 1 3 0第一轮合并后1、2、3 全在一个块里第二轮检查1 3时发现find(1) find(3)输出NO。这个流程和前面推演完全一致代码只是把我们脑内的逻辑机械化了。5. 我踩过的坑常见错误与排查思路5.1 数组开小 / 离散化后总点数算错我在写第一版时把 DSU 初始化为int(nums.size())后来改成int(nums.size() 1)时反而出错。原因很简单映射函数返回的下标是从 1 开始的因为我加了个1所以并查集大小至少要是不同点数 1否则最后一个点会越界。不要贪图省事把映射写成 0 起始然后又把 DSU 初始化为nums.size()两套规则混在一起最容易乱。我的建议是统一 1 起始并查集下标范围[1, size]初始化大小size 1。5.2 合并顺序错了导致“矛盾”漏判有人会想到我读入的时候如果是c0就向前找之前的c1合并这种一边读一边判断的思路实现起来很容易漏。因为并查集合并是有“后效性”的后面来的相等约束可能把两个曾经判定为“不在一起”的节点重新连在一起。如果你读入时就下结论必须同时记录和重查所有历史逻辑会退化得非常复杂。最好的办法永远是两趟扫描。第一次把相等合并干净第二次专门检查不等。如果你抱着“边读边查能少存一次”的侥幸心理WA 只是时间问题。5.3 unordered_map 的 reserve 与 max_load_factor离散化映射可以用unordered_mapint,int但我个人不太推荐在月赛里用它做映射因为哈希表在极端数据下可能会被卡到O(n^2)而且常数通常比lower_bound大。如果非要用记得先reserve(nums.size() * 2)并且设置max_load_factor(0.7)减少 rehash 次数。否则 2e5 个数全部插入时rehash 造成的耗时可能让你以为自己写了死循环。5.4 并查集初始化“漏了 iota”我在写DSU类的构造时第一次只resize了fa忘了把fa[i] i初始化结果运行起来每个点的祖先都是 0所有find都返回 0直接全线判断错误。这个问题在本地小样例可能不明显但一旦数据量变大所有点共享一个 0 根合并和查询结果完全乱套。建议写完 DSU 后立刻用一行小数据自测比如两个点一条相等约束输出find(a) find(b)是否为真。5.5 多组数据时忘记读入失败的处理上面的代码用了while (cin n m)这是很多竞赛选手的习惯。但如果你写成cin n m;后不判断输入流是否结束遇到评测器最后没有多余空格或换行时可能出错。好的习惯是检查cin的返回值或者用while (scanf(...) 2)。支持多组数据时尤其要注意nums和queries的生命周期。5.6 我实测下来最舒服的调试方式在比赛环境中如果 WA 了我不会急着打印大样例而是先构造两个超小样例3 2 1 2 1 1 2 0答案必须是NO。再来一个3 2 1 2 1 2 3 0答案是YES。这两个小用例能同时检验合并和检查两个阶段。如果这两个都过那基本可以排除并查集实现错误把注意力放到读入或者离散化上。我个人在实际操作中的体会是P15445 这类“名字浪漫、内核朴素”的题考察的并不是你会多少高级算法而是你能否一眼看穿等价关系用最朴素的并查集把逻辑链条整理清楚。很多人看完题解觉得很简单但自己在赛场上就是绕不出来原因往往不是没有学过并查集而是被“在一起”这个词诱导到字符串、图匹配或者动态规划的方向上去了。尤其是在月赛紧张的气氛里如果你能第一分钟就锁定并查集后面基本就是例行公事。如果后续遇到变式把题目改成“有的必须相同有的必须不同另外还有一些大小为 2 的集合需要满足奇偶性不同”那就要升级成带权并查集了。思路仍然是先合并确定关系再检查矛盾只是find路径压缩时要同步维护节点到根的异或值。这道题作为起点能让你把最核心的“离线 等价类”思想吃透后面再碰见加权的版本也不会慌。