Hard

题目描述

在这个问题中，有根树是一个有向图，满足：有且仅有一个节点（根节点）没有父节点，其他所有节点都有且仅有一个父节点。

给定一个有 n 个节点（节点值为 1 到 n）的有向图，该图原本是一棵有根树，但添加了一条额外的有向边。添加的这条边连接了两个不同的节点，且这条边不是原图中已存在的边。

结果图以二维数组 edges 的形式给出，其中 edges[i] = [ui, vi] 表示存在一条从 ui 指向 vi 的有向边，ui 是 vi 的父节点。

返回一条可以删除的边，使得结果图是一个有 n 个节点的有根树。如果有多个答案，返回在给定二维数组中最后出现的边。

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

提示：

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi

解题思路

这道题的关键是理解有根树的特性：每个节点最多有一个父节点，且整个图不能有环。

添加一条边后，可能出现两种情况：

  1. 某个节点有两个父节点：违反了有根树的定义
  2. 图中出现环：违反了树的定义

解题思路：

  1. 检测双父节点：遍历所有边，记录每个节点的入度。如果某个节点入度为2，说明有两个父节点
  2. 检测环：使用并查集来检测环的存在

具体步骤：

  1. 先找出所有可能导致双父节点的边（candidate1, candidate2）
  2. 如果没有双父节点问题，直接用并查集找第一个形成环的边
  3. 如果有双父节点问题：
    • 先尝试删除后出现的边（candidate2），看剩余图是否有环
    • 如果仍有环，则删除先出现的边（candidate1）

这种方法确保了我们总是返回最后出现的可删除边。

时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1);
        vector<int> candidate1, candidate2;
        
        // 检查是否有节点有两个父节点
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (parent[v] == 0) {
                parent[v] = u;
            } else {
                candidate1 = {parent[v], v};
                candidate2 = {u, v};
                edge[1] = 0; // 暂时移除第二个候选边
            }
        }
        
        // 并查集检查环
        for (int i = 1; i <= n; i++) parent[i] = i;
        
        for (auto& edge : edges) {
            if (edge[1] == 0) continue; // 跳过被移除的边
            int u = edge[0], v = edge[1];
            int pu = find(parent, u), pv = find(parent, v);
            if (pu == pv) {
                // 发现环
                return candidate1.empty() ? edge : candidate1;
            }
            parent[pv] = pu;
        }
        
        return candidate2;
    }
    
private:
    int find(vector<int>& parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
};

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = [0] * (n + 1)
        candidate1 = candidate2 = None
        
        # 检查是否有节点有两个父节点
        for i, (u, v) in enumerate(edges):
            if parent[v] == 0:
                parent[v] = u
            else:
                candidate1 = [parent[v], v]
                candidate2 = [u, v]
                edges[i][1] = 0  # 暂时移除第二个候选边
        
        # 并查集检查环
        parent = list(range(n + 1))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        for u, v in edges:
            if v == 0:  # 跳过被移除的边
                continue
            pu, pv = find(u), find(v)
            if pu == pv:
                # 发现环
                return candidate1 if candidate1 else [u, v]
            parent[pv] = pu
        
        return candidate2

public class Solution {
    public int[] FindRedundantDirectedConnection(int[][] edges) {
        int n = edges.Length;
        int[] parent = new int[n + 1];
        int[] candidate1 = null, candidate2 = null;
        
        // 检查是否有节点有两个父节点
        for (int i = 0; i < edges.Length; i++) {
            int u = edges[i][0], v = edges[i][1];
            if (parent[v] == 0) {
                parent[v] = u;
            } else {
                candidate1 = new int[] {parent[v], v};
                candidate2 = new int[] {u, v};
                edges[i][1] = 0; // 暂时移除第二个候选边
            }
        }
        
        // 并查集检查环
        for (int i = 1; i <= n; i++) parent[i] = i;
        
        foreach (var edge in edges) {
            if (edge[1] == 0) continue; // 跳过被移除的边
            int u = edge[0], v = edge[1];
            int pu = Find(parent, u), pv = Find(parent, v);
            if (pu == pv) {
                // 发现环
                return candidate1 ?? edge;
            }
            parent[pv] = pu;
        }
        
        return candidate2;
    }
    
    private int Find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent, parent[x]);
        }
        return parent[x];
    }
}

var findRedundantDirectedConnection = function(edges) {
    const n = edges.length;
    let parent = new Array(n + 1).fill(0);
    let candidate1 = null, candidate2 = null;
    
    // 检查是否有节点有两个父节点
    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i];
        if (parent[v]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n·α(n))，其中 α 是反阿克曼函数，在实际应用中可视为常数
空间复杂度O(n)，用于存储并查集的父节点数组

相关题目