1. 这个“格子游戏”到底在考什么第一次在《信息学奥赛一本通提高篇》的并查集专题里翻到 P1347 这道“格子游戏”我的第一反应是这题是不是得写个迷宫搜索或者用 BFS 不断找环读完题目才发现它跟你想象的那种复杂搜索完全不是一回事。它的经典之处在于把“网格图上有没有出现封闭回路”这个问题压缩成了“两个点是否已经在同一个连通块里”的并查集判断。题目大意通常是这样有一张由 n 行 n 列个点组成的网格图两位玩家轮流在相邻的两个格点之间连一条线段。谁先连出一个封闭的回路谁就获胜。如果所有线段都连完了还没有人连出回路就判平局。输入会给出网格大小 n 和一共连边的次数 m再按顺序给出每一次连线的两个端点坐标要求输出游戏是在第几步结束的以及是哪位玩家获胜。很多人看到“格子”“回路”“网格”这些词会下意识地往搜索算法方向想。但如果你对图论的基本结论比较敏感就会意识到在一个无向图中添加一条新边只有当它的两个端点原来已经连通时才会产生一个新的环。这个结论正是整道题的突破口。也就是说我们根本不需要真的把整张图画出来只需要实时维护“点与点之间的连通关系”。这篇文章我会从并查集的基础讲起把“为什么用并查集”“二维坐标怎么压成一维编号”“代码怎么写不会错”这几个问题一次讲透。不管你是刚学并查集的小白还是刷题时想快速复盘的老手都可以直接照着这套思路写代码、出样例、排查错误。1.1 题目卡片读完题先建模型拿到一道题我习惯先做一个最简信息表把题面“翻译”成数据结构能处理的语言输入规模n 行 n 列个点共 n × n 个节点m 次连边操作。每次操作给出一条线段的两个端点坐标 (x1, y1) 和 (x2, y2)两个端点一定相邻。判定成功某次操作完成后图中出现至少一个封闭回路。输出要求第一次形成回路的操作编号以及执行这一步的玩家编号如果始终没有回路输出平局。这题的“封闭回路”如果放到图论里就是无向图中的“环”。网格图本身是一个平面图玩家每次画的线段就是图的一条边。只要某一笔画下去之后图中存在一个环游戏立刻结束。把问题转化成这种语言之后后面所有算法选择都会变得顺理成章。1.2 为什么这道例题放在并查集章节《信息学奥赛一本通提高篇》把 P1347 放在并查集专题不是随便安排的。它想让你体会一件事图上的很多看似棘手的问题可以不建图、不搜索只用“连通块合并与查询”就能解决。先看暴力思路每加一条边就用 DFS 或 BFS 重新扫一遍整张图看有没有环。这样每次操作代价是 O(n²)总复杂度会达到 O(mn²)。题目稍微大一点就超时。而并查集的思路是每个点属于哪个连通块我们一直维护着新边加进来时只需要看两端点是否已经在同一个连通块。如果不在就把两个块合并如果在就说明已经存在一条从一端到另一端的通路新加这条边会直接把这条路闭合起来环就出现了。这个判断只需要两次 find 和一次合并近乎 O(1)和图的点数、边数是否巨大几乎没有关系。这就是竞赛题里最喜欢考的一点把问题抽象成连通性判断再用并查集高效维护。2. 核心思路用并查集判断“有没有闭环”2.1 并查集的基础操作并查集是一个非常“生活化”的数据结构。你可以把每个点看作一个人把“处在同一个集合”看作“这几个人的微信群已经拉好了”。两个群可以合并成一个也可以查询某两个人是不是在同一个群里。具体到代码上并查集只需要维护一个父亲数组 fa。最开始每个点都是独立的所以 fa[i] i。查询一个点属于哪个集合就是沿着父亲链往上找到根节点int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); // 路径压缩 }路径压缩的作用是每次查找时顺手把一路上的点都直接挂到根节点下面这样下次再查这些点时跳一次就能找到根。如果再加一个按秩合并可以让整棵树的高度保持很低。所谓按秩合并就是合并时把“矮树”接到“高树”下面避免树越并越深。void unite(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; if (rank[fx] rank[fy]) swap(fx, fy); fa[fy] fx; if (rank[fx] rank[fy]) rank[fx]; }有了这两个基础操作连通性问题就只剩下一行判断两个点的根是否相同。2.2 关键定理为什么新边两端已经在同一集合就等于出现闭环这个结论值得单独拿出来强调因为它是整道题的理论核心。考虑一张无向图如果两个顶点 u 和 v 之间已经存在一条路径那么此时再给它们之间加一条边会发生什么路径加上这条新边会构成一个首尾相接的闭合路线也就是一个环。反过来如果 u 和 v 不在同一个连通块里说明它们之间没有通路加一条边只会把两个连通块连接起来不可能凭空产生环。用并查集的语言描述就是“两个端点 find 结果相同 → 会成环find 结果不同 → 不会成环”。很多人容易把这个逻辑反着理解。他们可能会在合并之后再去检查结果永远查不出环来。这是初学者最典型的错误判环必须在合并之前完成。因为一旦合并了两个点就已经属于同一个集合之后无论怎么看都“像是本来就连通”。正确的顺序永远是先找根、比较根、再决定是否合并。2.3 二维坐标变成一维编号并查集处理的是“一维编号”但题目给的是平面坐标 (x, y)。所以第一步是把每个点映射成一个整数 ID。常见写法是编号 (x - 1) * n y假设 n 3也就是一个 3 行 3 列的点阵那么坐标编号(1,1)1(1,2)2(1,3)3(2,1)4(2,2)5(2,3)6(3,1)7(3,2)8(3,3)9为什么是(x - 1) * n y而不是其他公式因为二维数组按行存储时第 x 行第 y 列的位置本来就在(x - 1) * n y。这个公式最直观也最不容易算错。要注意的是题目中的坐标如果从 0 开始编号公式就变成x * n y 1或者x * n y具体取决于你希望 ID 从 0 还是从 1 开始。刷题时建议统一用 1 起始因为 fa 数组初始化的循环写起来更方便。3. 代码怎么写才不踩坑3.1 并查集核心函数怎么写先把代码骨架搭好。因为我用的编号范围是 1 到 n × n所以数组大小至少是n * n 5。如果题目给出的 n 最大是 200那40005是稳妥的如果 n 可能到 1000就得开到 1000005。千万不要只开n 5否则下标越界会让你调试到怀疑人生。核心函数可以写成这样const int MAXN 40005; int fa[MAXN], rnk[MAXN]; int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void unite(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; if (rnk[fx] rnk[fy]) swap(fx, fy); fa[fy] fx; if (rnk[fx] rnk[fy]) rnk[fx]; }这里用一个rnk数组记录树的“高度”。即使不写按秩合并只写路径压缩通常也能过题但加上按秩合并能让代码的复杂度分析更漂亮也避免在极端数据下退化成链。3.2 主流程先判断再合并主程序的逻辑是逐条处理输入边。每读入一条边先把两个端点坐标转成 ID然后比较它们的根。如果根相同说明这一步会形成闭环立刻输出答案并结束程序否则合并两个点。用伪代码描述就是读入 n, m 初始化 fa[1..n*n] for i 1 to m: 读入 x1, y1, x2, y2 a id(x1, y1) b id(x2, y2) if find(a) find(b): 输出 i 输出第 i 步操作的玩家 return 0 else: unite(a, b) 输出平局这个流程看起来简单但有一个细节值得注意一旦在某一轮判断出胜负要立刻 return不要再继续处理后面的边。有些同学会在判断出结果后继续循环结果后面又读入了一些边导致答案被覆盖或者输出混乱。虽然提前 return 会“浪费”掉尚未读入的输入但程序已经退出不再需要那些数据所以没有任何副作用。3.3 完整参考代码下面是一份可以直接提交的 C 代码我加了一些注释方便你对照理解#include bits/stdc.h using namespace std; const int MAXN 40005; int fa[MAXN], rnk[MAXN]; int n, m; int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void unite(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; if (rnk[fx] rnk[fy]) swap(fx, fy); fa[fy] fx; if (rnk[fx] rnk[fy]) rnk[fx]; } int id(int x, int y) { return (x - 1) * n y; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; int total n * n; for (int i 1; i total; i) { fa[i] i; rnk[i] 0; } for (int step 1; step m; step) { int x1, y1, x2, y2; cin x1 y1 x2 y2; int a id(x1, y1); int b id(x2, y2); if (find(a) find(b)) { cout step \n; if (step % 2 1) cout 1 \n; else cout 2 \n; return 0; } unite(a, b); } cout draw\n; return 0; }这段代码里的输出格式我写成“先输出步数再输出玩家编号”。因为不同 OJ 对输出格式的要求可能不太一样有的会要求输出“玩家1”“玩家2”这样的字符串。你只需要把最后的 if 分支稍微改一改即可核心算法完全不变。4. 调试、样例与常见问题4.1 一个能跑出结果的样例演示只看代码不手动跑样例永远学不会并查集。我准备了一个 3 × 3 点阵的小样例这里可以非常直观地看到“闭环到底是什么时候出现的”。输入3 4 1 1 1 2 2 1 2 2 1 1 2 1 1 2 2 2四步操作分别是连 (1,1) 和 (1,2)连 (2,1) 和 (2,2)连 (1,1) 和 (2,1)连 (1,2) 和 (2,2)前三步连接起来后四个点 (1,1)、(1,2)、(2,1)、(2,2) 已经被三条边连成了一个“U”形。第四步连的是右上方 (1,2) 到右下方 (2,2) 的边等于把缺口补上形成一个正方形闭环。所以第 4 步结束后游戏结束执行第 4 步的是玩家 2。输出就是4 2如果你把这里的点和边画在纸上会看得非常清楚。画图也是我调试这类问题时最喜欢用的方式网格题一旦抽象成编号脑子容易绕但画出来就一目了然。4.2 不会闭环的平局样例再看一个不会出现闭环的例子。如果操作路径只是一条简单的折线没有回头闭合那游戏就会一直持续到最后都没有赢家。输入3 3 1 1 1 2 1 2 2 2 2 2 2 3这三条边形成了一条从 (1,1) 到 (1,2)、再到 (2,2)、再到 (2,3) 的折线。所有点都是新加入的每次合并都会把两个不同的连通块连起来因此不会产生环。最终输出平局。这里输出成什么取决于题目要求我这里输出“draw”。平局样例的价值在于验证程序流程不会在 m 次循环结束后崩溃也不会因为没有提前 return 而多输出一次结果。4.3 高频错误速查表我把自己在刷题和帮别人看代码时遇到过的错误整理成一张表你可以直接收藏起来写代码时对照检查。错误类型具体表现正确做法数组开小了只开了 n 个位置却要存 n × n 个点数组大小至少为 n * n 5编号公式写错用了 x * n y导致不同坐标映射到同一个编号统一用 (x - 1) * n y先合并再判断find(a) 和 find(b) 永远相等必须先用 find 判断再决定是否合并输出玩家号搞反把奇数步输出为玩家 2奇数步是玩家 1偶数步是玩家 2提前 return 条件不写找到环后继续跑输出被覆盖判断成立立刻 return 0多组数据未初始化上一组数据的 fa 污染下一组每组数据开始前重新初始化 fa 和 rnk坐标从 0 开始但公式没变边界点无法访问先确认坐标起始编号再选用对应公式这些坑看起来都不大但每一个都足以让你在一道你们明明会做的题上面卡很久。尤其是“先合并再判断”这个问题属于典型的逻辑顺序错误代码不会报错但答案永远不对排查时最让人头疼。4.4 数据规模与复杂度预估并查集单次 find 操作在路径压缩后是近似 O(1)准确说是反阿克曼函数级别。整道题要做 m 次操作每次操作最多两次 find一次合并所以总复杂度是 O(m α(n²))可以认为就是 O(m)。如果 n 是 200n² 40000可以很轻松跑完。如果 n 是 1000n² 1000000也没问题。真正需要注意的反而是输入读取。当 m 很大的时候用cin如果不关同步容易被 IO 卡掉一部分时间。我这里写了ios::sync_with_stdio(false)和cin.tie(nullptr)就是避免这个问题。如果你的 OJ 是老旧环境换成scanf也可以。5. 从“格子游戏”看并查集的延展应用5.1 最小生成树里的“老朋友”如果之前学过 Kruskal 最小生成树算法你会发现它跟你现在写的“判环”逻辑几乎一模一样。Kruskal 的做法是把所有边按权值排序从小到大逐个尝试加入。加入之前先看这条边的两个端点是否已经在同一个连通块里。如果已经连通就跳过这条边因为它加入后会形成环如果没连通就把它加入树中并合并两个端点。你看底层逻辑连措辞都没变。所以 P1347 这道“格子游戏”不只是孤立的一道例题它是整个生成树理论里“删边判环”思想的基础。把这道题吃透后面学 Kruskal、学差分约束、学带权并查集的时候都会轻松很多。5.2 带权并查集与更多扩展并查集能维护的不只是“是否连通”。在很多更难的题里同一个集合里面的点之间还有数值关系比如“A 比 B 大多少”“A 和 B 的性别关系”“A 和 B 的距离”。这时候你需要在 find 和合并的过程中额外维护一个权重数组记录每个节点到根的相对值这就成了带权并查集。经典题“食物链”“银河英雄传说”“奇偶游戏”都是这个方向。它们的共同点是表面上题目问的不是连通性而是“这个关系和那个关系是否矛盾”但只要把每个关系看成一条带权边把“矛盾”看成“同一个集合里出现冲突信息”就能用并查集解决。格子游戏其实已经提前为你演示了这个思路的起点把几何问题抽象成边和连通块。5.3 竞赛中怎么快速识别“并查集题”刷题刷多了以后你看到一道题会自然产生一种“题型直觉”。以下几个信号出现时我会优先考虑并查集题目涉及“动态加边”并且需要判断“什么时候出现环”。题目问“两个元素是否已经在同一个集合/阵营/组织里”。题目给出若干条“关系”要求检测关系之间是否存在矛盾。题目能用“连通块”描述状态且合并操作比删除操作更容易实现。格子游戏就是第一种情况的典型代表。你只要记住“加边成环等价于两端点已连通”这个结论以后遇到类似题目就能少走很多弯路。6. 我刷这道题时的一些个人习惯6.1 写代码前先写“判环函数”我强烈建议你写代码前先单独用一个函数表达判环逻辑而不是把 find 和比较全部堆在 main 里。哪怕你的最终代码只是几行也值得先想清楚每一轮循环要做什么、什么时候输出、输出之后是否立即退出。我会在纸上先写一句类似“若 find(a)find(b) 则输出并把 return 置为 true”的东西再动键盘。这样写出来的代码结构清晰出错后也容易定位。6.2 用最小样例和大样例各测一次最小样例就是能让程序跑通的最小输入比如 2 × 2 点阵两条边就出环。大样例则用来检查数组边界和性能。很多时候小样例帮你验证逻辑大样例帮你验证内存。如果你没有现成的大数据可以自己写一个随机生成器每次在 n × n 的范围内随机生成相邻点对然后跑一遍程序看会不会越界或超时。我在实测这类题时还有一个习惯把 find 函数设一个计数器统计它被调用的总次数。如果这棵树退化成了链调用次数会明显异常地多。路径压缩正常情况下会让查询次数非常接近点数的常数倍算是给自己吃一颗定心丸。6.3 最后一次分享一个实测小技巧在调试这种“边读入边判断”的题目时很多人喜欢输出一些调试信息比如“当前合并了哪两个点”“当前根是谁”。这没问题但我建议把调试信息打上“步数”前缀也就是每一步操作都先输出step 某数。因为一旦输出结果提前 return你才能知道程序是在哪一步退出的。这个习惯帮我在很多环形结构的问题里迅速定位错误来源。格子游戏这道题本身不难但它就像是一把钥匙打开了“用并查集解决图论问题”这扇门。掌握了坐标压缩和判环顺序以后再看到网格图、关系题、矛盾检测题你都能比别人更快一步想到并查集。这种从单一题目里提炼出通用模型的感觉才是刷竞赛题最让人上瘾的地方。