LeetCode 685题解：有向图中冗余边的识别与删除

本文深入解析了 LeetCode 第 685 题 “Redundant Connection II”。题目要求在一个有向图中，找到并移除一条冗余边，使其能够转换为一棵合法的有根树。我们将重点探讨如何运用并查集算法，并结合有向图的特殊性质，优雅地解决这个问题。

题目描述与链接

给定一个包含 n 个节点的有向图（节点编号从 1 到 n），该图由 n 条边（edges[i] = [a_i, b_i] 表示从 a_i 指向 b_i 的有向边）组成。该图在移除恰好一条边后，可以成为一棵所有节点都指向同一方向的有根树。请找出需要移除的那条边。如果存在多个答案，则返回在原数组中下标更大的那条边。

原题地址：https://leetcode.com/problems/redundant-connection-ii/

核心解题思路

我们可以把问题转化为分析在一棵有根树上添加一条边后，产生的两种违规情况：

1. 入度为2（一个节点有两个父节点）：如果添加的边指向一个非根节点，则该节点会出现两个父节点。此时，冗余边必然是使该节点入度变为2的两条边之一。
2. 有向环：如果添加的边指向根节点，则图中会形成一个包含根节点的有向环。此时，环上的任何一条边被移除都可以使图恢复为树。

基于此，我们的算法可以设计如下：

1. 父节点记录与冲突检测：遍历所有边，记录每个节点的父节点。如果某个节点被第二次指定父节点，则发现了“入度为2”的冲突。我们将冲突的两条边 [A, to] 和 [B, to] 缓存为候选答案（[A, to] 为先出现的边），并暂时屏蔽后出现的边 [B, to]，以便后续判断哪条边实际造成了环。
2. 并查集找环：将图视为无向图，使用并查集（Union-Find）进行遍历（跳过被屏蔽的边）。
   • 如果合并过程中没有发现环，且存在候选边，则说明被屏蔽的那条边 [B, to] 是冗余边。
   • 如果在合并边 [x, y] 时发现它们已在同一集合中（即形成了环）：
     • 若不存在候选边（即没有入度2冲突），则当前边 [x, y] 就是冗余边。
     • 若存在候选边，则说明未屏蔽的那条候选边 [A, to] 是冗余边。

代码实现 (C++)

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1, -1); // 记录每个节点的直接父节点
        vector<int> unionSet(n + 1);   // 并查集数组
        vector<vector<int>> candidates; // 存储候选边（当有节点出现两个父节点时）

        // 初始化并查集，每个节点自成集合
        iota(unionSet.begin(), unionSet.end(), 0);

        // 第一步：检查是否有节点入度为2，并标记候选边
        for (auto& e : edges) {
            int from = e[0], to = e[1];
            if (parent[to] != -1) {
                // 节点 `to` 已经有了父节点，发现冲突
                candidates.push_back({parent[to], to}); // 第一条指向 to 的边
                candidates.push_back({from, to});       // 第二条指向 to 的边
                e[0] = e[1] = -1; // 屏蔽当前这条边（第二条边）
                break;
            }
            parent[to] = from;
        }

        // 并查集查找函数（带路径压缩）
        function<int(int)> find = [&](int x) -> int {
            return unionSet[x] == x ? x : unionSet[x] = find(unionSet[x]);
        };

        // 第二步：并查集遍历找环（跳过被屏蔽的边）
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            if (x == -1) continue; // 跳过被屏蔽的边

            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                // 发现环
                if (candidates.empty()) {
                    // 情况2：没有入度2冲突，当前边即是冗余边
                    return {x, y};
                } else {
                    // 情况1：有入度2冲突，且未屏蔽的候选边导致了环
                    return candidates[0];
                }
            }
            // 合并集合
            unionSet[rootX] = rootY;
        }

        // 遍历完未发现环，说明被屏蔽的候选边是冗余边（情况1的另一分支）
        return candidates[1];
    }
};

复杂度分析

• 时间复杂度：O(n α(n))，其中 α(n) 是反阿克曼函数，可近似认为是一个常数。我们进行了两次近乎线性的边遍历。
• 空间复杂度：O(n)，用于存储父节点数组和并查集数组。在解决这类图论问题时，并查集因其高效性常被用作核心数据结构。