在 n×n 点阵上按顺序加边，加边后成圈等价于新边两端已经连通；连通只合并不分裂，用并查集增量维护，第一条两端同块的边就是答案。
OJ: roj
题目 ID: 1347
难度:普及-
标签:并查集图论环检测python
创建: 2026-09-30 06:22
更新: 2026-10-13 22:33
前置题目
luogu P1551亲戚B 把 A 教的并查集合并后比较代表元的判定直接用作 unite(u, v) 返回 False（两端已同根）的封圈条件，只是把「是否同组」这一问改挂到「加边是否成圈」上luogu P3367【模板】并查集A 作为并查集模板教的 find 与「比较两个根是否相同」，在 B 里直接充当封圈判据：`unite(u, v)` 返回 `False`（两端已同根）即连通性已存在，于是输出步数，否则合并两棵树。luogu P8654[蓝桥杯 2017 国 C] 合根植物A 教的并查集把两点合并到同一集合并判定是否原本已同集合，B 把同一判定直接用作“两端同根即成圈”的封圈条件，只是把 blocks-- 换成输出步数
题目描述
n×n 点阵上依次加入 m 条相邻点之间的无向边，‘D’ 表示向下，‘R’ 表示向右，边不重复。输入 n、m 与每条边起点 (x,y) 和方向；输出首次成圈的步数 i，若 m 条边加完仍无圈则输出 draw。样例输入 3 5 加 5 条边后输出 4。数据范围 n ≤ 200。
思路
加边后成圈等价于新边两端已经连通。边只增不减，连通性只合并不分裂，用并查集增量维护；按顺序处理每条边，若两端同根说明该步封圈，否则合并两块。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 06:23
# update_at: 2026-10-13 22:28
import sys
class DSU:
"""并查集 (Disjoint Set Union)"""
def __init__(self, n: int):
# 1-indexed, fa 初始指向自己，sz 初始为 1
self.fa = list(range(n + 1))
self.sz = [1] * (n + 1)
def find(self, x: int) -> int:
"""查找根节点，两趟路径压缩：先走到根，再把整条路径挂到根上"""
root = x
while self.fa[root] != root:
root = self.fa[root]
while self.fa[x] != root:
self.fa[x], x = root, self.fa[x]
return root
def same(self, x: int, y: int) -> bool:
"""判断 x 和 y 是否属于同一个集合"""
return self.find(x) == self.find(y)
def unite(self, x: int, y: int) -> bool:
"""按大小合并两个集合 (小树挂大树)；已在同一集合返回 False"""
fx, fy = self.find(x), self.find(y)
if fx == fy:
return False
if self.sz[fx] < self.sz[fy]:
fx, fy = fy, fx
self.fa[fy] = fx
self.sz[fx] += self.sz[fy]
return True
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n, m = int(next(data)), int(next(data))
width = n + 1 # 真实数据有越界边（x=n 向下 / y=n 向右）
dsu = DSU(width * width) # 点 (x, y) 编号 (x-1)*width + y
step = {b"D": width, b"R": 1} # D 是向下走一行，R 是向右走一格
for i in range(1, m + 1):
x, y = int(next(data)), int(next(data))
u = (x - 1) * width + y
v = u + step[next(data)]
if not dsu.unite(u, v): # 两端已连通，加这条边就成环，它就是封圈那一步
print(i)
return
print("draw")
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 11:16
* update_at: 2026-10-13 22:33
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
// 并查集竞赛精简版（不用 struct）：路径压缩 + 按大小合并
// 口诀：find 找根压到底，unite 小树挂大树
// 易错点：init 别只写 fa[i] = i，sz[i] 也要置 1；合并后 sz 只在新根上有效
// 和别的模板一起用时 maxn 只留一份
const int maxn = 205 * 205;
int fa[maxn], sz[maxn]; // sz[x] 仅在根上有效
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}
// 查 x 的根，顺手把整条链压到根上
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
// 小树挂大树，返回是否真的发生了合并
bool unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
return true;
}
int n, m;
int W; // 点阵实际宽度，含虚拟外圈
int main() {
scanf("%d %d", &n, &m);
W = n + 1; // 真实数据里有 x=n 向下 / y=n 向右的越界边，多开一圈
init(W * W); // 编号空间为 W*W，留出越界边所在的一圈
for (int i = 1; i <= m; ++i) {
int x, y;
char dir[2];
scanf("%d %d %1s", &x, &y, dir); // 读入一个非空白字符
int u = (x - 1) * W + y; // 点 (x, y) 的编号，1-based
int v;
if (dir[0] == 'D') v = u + W; // 向下连到下一行同列
else v = u + 1; // 'R'，向右连到同一行下一列
if (!unite(u, v)) { // 两端已在同一块，加这条边必成环
printf("%d\n", i);
return 0;
}
}
printf("draw\n");
return 0;
}