冗余连接问题为什么适合用并查集？

简化版

冗余连接是在一棵树里多加了一条边，要求找出造成环的那条边。用并查集逐条处理边，如果两个端点已经在同一个集合里，再连这条边就会形成环，这条边就是冗余边。

详细版

并查集维护当前已经连接的连通块。对每条边 (u, v)，先 find(u) 和 find(v)：如果根不同，说明这条边连接了两个不同连通块，可以 union；如果根相同，说明 u 和 v 之前已经连通，再加这条边就产生环，返回它。

因为题目通常保证原图是树加一条边，所以第一条 union 失败的边就是答案。路径压缩和按秩合并后，时间复杂度近似 O(E)，空间复杂度 O(V)。

完整版教学

一、为什么树加一条边一定会成环

一棵有 n 个节点的树有两个关键性质：连通，并且恰好有 n - 1 条边。任意两个节点之间只有一条简单路径。如果再加一条连接已有两个节点的边，就会和原来的那条路径围成一个环。

原树路径: 1 - 2 - 3
新增边:   1 ----- 3

环: 1 -> 2 -> 3 -> 1

冗余连接问的不是“图里有没有环”，而是“哪条输入边第一次让环出现”。这非常适合按输入顺序动态维护连通性。

二、并查集维护的是连通块

并查集有两个核心操作：find(x) 找 x 所在集合的代表节点，union(a,b) 合并两个集合。对于无向图，如果两个点已经在同一个集合里，说明它们之间已经有路径；再加入一条直接边，就必然形成环。

情况	find(u) 与 find(v)	动作	含义
不同集合	不相等	union	连接两个连通块
同一集合	相等	返回该边	这条边制造环

例如边序列 [1,2] [1,3] [2,3]：前两条边把 1、2、3 合成一个集合；处理 [2,3] 时发现 2 和 3 已经连通，所以 [2,3] 是冗余边。

三、代码实现骨架

并查集实现要包含路径压缩，否则链式父指针可能退化。按秩合并或按大小合并可以进一步降低树高。

int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    int[] parent = new int[n + 1];
    int[] rank = new int[n + 1];
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int[] e : edges) {
        if (!union(parent, rank, e[0], e[1])) return e;
    }
    return new int[0];
}

int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

boolean union(int[] parent, int[] rank, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return false;
    if (rank[ra] < rank[rb]) parent[ra] = rb;
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    return true;
}

这里 union 返回 false 表示“合并失败”，不是程序失败，而是两个端点已经属于同一集合。

四、为什么不用 DFS 每次判环

当然可以每加入一条边就 DFS 检查 u 和 v 是否已连通，但这样最坏会变成 O(E(V+E))。并查集把“是否连通”压缩成近似常数级查询，更适合边按顺序加入的题。

逐边 DFS:
edge1 -> 搜一次
edge2 -> 搜一次
...
edgeE -> 搜一次

并查集:
edge -> find + union

如果 E = 10000，逐边 DFS 可能重复扫描大量已有边；并查集基本只是在父指针数组上跳转，性能差距很明显。

五、和普通环检测的区别

普通无向图环检测常用 DFS，需要记录父节点，避免把来时边误判成环。冗余连接则利用题目“树加一条边”的特殊结构，只要发现一条边连接了已连通的两个端点，就能确定它是答案。

问题	推荐方法	关注点
无向图是否有环	DFS 或并查集	是否存在环
找树中多出来的边	并查集	哪条边首次连接同集合
有向图依赖成环	DFS 三色或拓扑	回边或入度剥离

面试时要讲清楚“无向边 + 动态加入 + 连通性查询”这三个信号，它们共同指向并查集。

六、复杂度与编号边界

路径压缩加按秩合并后，find/union 的均摊复杂度是 O(α(V))，几乎可以看成常数。处理 E 条边，总时间是 O(E α(V))，空间是 O(V)。

题目常见节点编号从 1 到 n，所以数组开 n + 1。如果节点编号不连续，例如字符串账号或任意整数，就用哈希表把节点映射到连续编号，或者直接用 Map<T,T> 实现 parent。

七、常见误区与追问

记忆钩子：并查集不是在找路径细节，而是在问“这两个点之前是不是已经通了”；已经通了还加边，就是环。

误区：看到环就一定用 DFS。 这题按边逐步加入，判断端点是否已连通更直接，并查集更贴合。
误区：union 返回 true 时返回边。 union 成功表示两个集合原本不连通，这条边合法；union 失败才是冗余边。
误区：数组只开到 edges.length。 如果节点编号从 1 开始，通常要开 n + 1，否则编号 n 会越界。
追问：如果有多条冗余边怎么办？ 经典题保证只有一条；若不保证，按题意可能返回第一条造成环的边，或返回最后一条，需要明确输入要求。
追问：有向图冗余连接还能这样做吗？ 有向图还涉及入度为 2 和有向环，需要额外分类讨论，不能直接套无向并查集。
追问：为什么路径压缩有效？ 每次 find 都把路径上的节点直接挂到根上，后续查询会越来越接近 O(1)。

八、加强记忆

冗余连接抓住三个词：无向图、树多一边、动态连通性。按输入顺序处理边，两个端点根不同就合并，根相同就说明已有路径，再加这条边会闭环。并查集让“是否已连通”变成近似常数查询，是这题比逐次 DFS 更优雅的原因。

简化版

详细版