跳到主要内容

LeetCode 684. 冗余连接

本节目标

利用并查集的重复合并失败，定位无向图中第一条形成环的边。

这是连通性、并查集与二分图中“把重复合并当作成环信号”的母题。树中任意两点之间本来只有一条路径；加入一条两端已连通的边，就闭合成环。

查看 LeetCode 原题

题意与约束​

给定原本是一棵树、后又多加一条边得到的无向图，按输入顺序返回最后一条可删的冗余边。节点编号从 1 开始，边数量足以作为 DSU 容量上界。题目中的冗余边也可能是重复给出的同一对端点：第二次合并必须识别为失败。

直接思路与瓶颈​

每读一条边就用 DFS 在已处理的图里寻找两端是否已有路径，能够判断成环，但每次查询都要重新走已有边；边逐渐增多时总成本最坏为 O(E(V+E))。我们只关心“此前是否已连通”，无需保存那条路径，因而用集合代表元维护更直接。

图模型与算法推导​

依次处理边 (u, v)。若 find(u) != find(v)，两端尚未连通，把两个集合合并，继续保持一片森林；若根已经相同，处理过的边中已有一条 u 到 v 的路径，再加入当前边必形成环，因此当前边就是答案。

这里 unite 的布尔返回值比单独调用两次 find 更不容易漏更新：成功表示真正连接了两棵树，失败表示没有产生新连通性。

正确性依据​

归纳处理过的边。开始没有边，是森林。每次合并不同集合等价于给两棵树连一条边，仍是森林；只有两端已在同一树时，当前边与树中已有路径构成唯一新环。题目保证仅多一条边，所以第一次合并失败的边正是应删除的冗余连接。

样例执行过程​

对边序列 [[1,2],[1,3],[2,3]]，源码按边数分配 parent = [0,1,2,3]，其中 0 未使用。处理 (1,2)：根为 1、2，合并后 parent[2] = 1；处理 (1,3)：根为 1、3，合并后三点同属根 1。处理 (2,3) 时，路径压缩后 find(2) = find(3) = 1，unite 返回 false，立即返回当前边 [2,3]。

代码实现​

C++17
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class DisjointSet {
    vector<int> parent;
    vector<int> size;

public:
    explicit DisjointSet(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

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

    bool unite(int first, int second) {
        int rootFirst = find(first);
        int rootSecond = find(second);
        if (rootFirst == rootSecond) return false;
        if (size[rootFirst] < size[rootSecond]) swap(rootFirst, rootSecond);
        parent[rootSecond] = rootFirst;
        size[rootFirst] += size[rootSecond];
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        DisjointSet sets(static_cast<int>(edges.size()) + 1);
        for (const auto& edge : edges) {
            if (!sets.unite(edge[0], edge[1])) return edge;
        }
        return {};
    }
};

测试既检查普通三角环，也检查在已合并 1 与 2 后再次加入 (1, 2) 的重复合并；两种情况都应在 unite 返回 false 时返回当前边。

复杂度分析​

每条边进行常数次 find/unite，时间为 O(n α(n))；parent 与 size 占 O(n) 空间。

边界与易错点​

  • 节点从 1 编号，DSU 应额外保留索引 0 或按最大编号分配。
  • 返回输入中触发失败的原边顺序，不要排序端点。
  • 同根时不能再更新 size 或 parent。
  • 这里适用于只加边；若边会被删除，普通 DSU 不可逆。

模式迁移​

“加一条边是否形成环”“动态加入关系后是否已连通”都可直接复用。若要真正输出环上的全部节点，需要在图中保存路径，不是 DSU 单独能提供的信息。