算法认知学习实验室
第 8 章 · 图与并查集 · Unit 11
仅本次页面有效
08·11
冗余连接在线判环 · Union-Find
LeetCode #684 · Redundant Connection
一条边到来时，先问：它的两端已经连通了吗？
并查集不需要保存完整路径。它把此前接受的边压缩成“属于哪个连通分量”这一份状态：若新边两端的代表元相同，既有路径与新边共同闭合成环，这条边就是冗余连接。
11
从合并到在线判环
Unit 10 用成功合并次数统计省份；本单元把 union 的失败转化为答案。
已恢复上次学习现场
本单元状态契约
find(a) == find(b) 当且仅当节点 a 与 b 已经被此前接受的边连通。每条边必须先查询两端根，再决定合并或返回。
六阶段路线
图模型 → 朴素判环 → 在线并查集 → 不变量与错误 → Python 联动 → #990 约束迁移。
树 + 一条边
原图从一棵树出发，多加入一条无向边，因此会出现且只出现一个环。
在线处理
边按输入顺序到达，只使用此前边形成的状态判断当前边。
冗余边
删除后仍能保持全部节点连通且无环的边。本题要求返回输入中最后出现的可删除边。
Union 失败
两端根相同，无需合并；当前边闭合环并成为答案。