每日算法系列【LeetCode 685】冗余连接 II

简介: 每日算法系列【LeetCode 685】冗余连接 II

题目描述

在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。

输入一个有向图,该图由一个有着  个节点(节点值不重复 )的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边 的元素是一对 ,用以表示有向图中连接顶点  和  和顶点的边,其中父节点  是子节点  的一个父节点。

返回一条能删除的边,使得剩下的图是有  个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

示例1

输入:
[[1,2], [1,3], [2,3]]
输出:
[2,3]
解释:
  1
 / \
v   v
2-->3

示例2

输入:
[[1,2], [2,3], [3,4], [4,1], [1,5]]
输出:
[4,1]
解释:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

提示

  • 输入的二维数组大小在  到 。
  • 二维数组中的整数在  到  之间,其中  是输入数组的大小。

题解

这题是上一道题 每日算法系列【LeetCode 684】冗余连接 的进阶版,区别就是无向图变成了有向图。

上一道题解说过,无向图能构成一棵树的条件是没有环,那么有向图的条件是什么呢?

首先还是得没有环,其次因为是边是有向的,所以一个结点只能有一个父结点(也就是入度为 )。那么这题解法就有了。

  • 首先判断有没有入度为  的结点,如果有的话,那两条边一定有一条得删掉。
  • 按照出现时间从后到前看那两条边,删掉其中一条之后是否能构成一棵树(也就是无环)。如果删掉了无环,那就直接返回这条边作为答案。
  • 如果入度全是  ,那就直接按照出现时间从前到后看添加了哪一条边之后开始出现了环,那么那条边就是答案。

判断能否构成一棵树的话还是用并查集,唯一区别就是不需要用按秩合并的优化了,而且给定有向边 ,只能把  接在  下面。

代码

c++

class Solution {
public:
    static const int N = 1010;
    int f[N], degree[N];
    int n;
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        n = edges.size();
        memset(degree, 0, sizeof degree);
        for (auto e : edges) ++degree[e[1]];
        for (int i = n-1; i >= 0; --i) {
            if (degree[edges[i][1]] == 2 && !wrongEdge(edges, i).size()) {
                return edges[i];
            }
        }
        return wrongEdge(edges, n);
    }
    vector<int> wrongEdge(vector<vector<int>>& edges, int except) {
        init();
        for (int i = 0; i < n; ++i) {
            if (i == except) continue;
            int u = edges[i][0], v = edges[i][1];
            if (same(u, v)) return edges[i];
            join(u, v);
        }
        return {};
    }
    void init() {
        for (int i = 1; i <= n; ++i) {
            f[i] = i;
        }
    }
    int find(int u) {
        return u==f[u] ? u : f[u]=find(f[u]);
    }
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        f[v] = u;
    }
    bool same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
};

python

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        self.n = len(edges)
        degree = [0] * (self.n+1)
        for u, v in edges:
            degree[v] += 1
        for u, v in edges[::-1]:
            if degree[v] == 2 and len(self.wrongEdge(edges, [u, v])) == 0:
                return [u, v]
        return self.wrongEdge(edges, [])
    def wrongEdge(self, edges, ex):
        self.f = [i for i in range(self.n+1)]
        for u, v in edges:
            if [u, v] == ex:
                continue
            if self.same(u, v):
                return [u, v]
            self.join(u, v)
        return []
    def find(self, u):
        if u == self.f[u]:
            return u
        self.f[u] = self.find(self.f[u])
        return self.f[u]
    def join(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:
            return
        self.f[v] = u
    def same(self, u, v):
        u, v = self.find(u), self.find(v)
        return u == v
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
13天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
3月前
|
自然语言处理 算法 数据挖掘
【数据挖掘】十大算法之PageRank连接分析算法
文章介绍了PageRank算法的基本概念和数学模型,包括如何通过一阶马尔科夫链定义随机游走模型以及如何计算网页的重要性评分,并提供了PageRank迭代算法的具体步骤。
74 0
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
24 2
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
60 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
79 0
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
42 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0