[路飞]_leetcode-685-冗余连接 II

简介: leetcode-685-冗余连接 II

网络异常,图片无法展示
|


[题目地址][B站地址]


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


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


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


返回一条能删除的边,使得剩下的图是有 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


解题思路


本题依然是一个连通性问题,只不过在连通性的基础上添加了有向性,使问题变得更复杂了。


本题中有向图的连接方式可以分为三种类型,要根据连接方式分类讨论其返回值。


  1. 示例1 中的连接情况,有一个子节点有两个父节点,定义为双入度情况
  2. 示例2 中的连接情况,连接形成了环,定义为成环情况
  3. 示例中未给出的情况,即成环,又有双入度的情况


针对双入度的情况,需要返回的边是形成双入度的边。


针对成环的情况,需要返回的边是成环的边。


针对即成环,又有双入度的情况,需要返回的是双入度边的子节点及其父节点组成的边。


动画演示


网络异常,图片无法展示
|


代码实现


// 并查集
class UnionSet {
  // 初始化list
  constructor(n){
    this.list = Array(n);
    for(let i = 0;i<n;i++){
      this.list[i] = i;
    }
  }
  // 查找元素所在集合并进行路径压缩
  find(x){
    if(this.list[x] === x) return x;
    const root = this.find(this.list[x])
    this.list[x] = root;
    return root;
  }
  // 合并子节点集合到父节点集合
  merge(rootA,rootB){
    this.list[rootB] = rootA;
  }
}
var findRedundantDirectedConnection = function(edges) {
  // 获取顶点数量
  const len = edges.length,
  // 根据顶点数量创建并查集
  unionset = new UnionSet(len+1),
  // 根据顶点数量创建parent数组,维护顶点父节点
  parent = Array(len+1);
  for(let i = 1;i<=len;i++){
    parent[i] = i;
  }
  // 初始化双入度边及成环边的下标
  let doubleInd = -1,circleInd = -1;
  // 遍历输入数组
  for(let i = 0;i<len;i++){
    const [a,b] = edges[i];
    // 如果当前子节点已经被作为子节点连接过,则此时形成了双入度
    if(parent[b]!==b) doubleInd = i;
    else{
      // 否则更新子节点的父节点
      parent[b] = a;
      // 如果两个顶点在同一个集合,则此时形成了环
      const rootA = unionset.find(a),
      rootB = unionset.find(b);
      if(rootA===rootB) circleInd = i;
      // 否则将子节点所在集合合并到父节点所在集合
      else unionset.merge(rootA,rootB)
    }
  }
  // 如果当前只是成环的情况,返回成环的边
  if(doubleInd===-1) return edges[circleInd]
  // 如果只是双入度的情况,返回双入度的边
  if(circleInd===-1) return edges[doubleInd]
  // 如果是成环且双入度的情况,返回双入度子节点及其父节点组成的边
  const child = edges[doubleInd][1];
  return [parent[child],child]
};
复制代码


至此我们就完成了 leetcode-685-冗余连接 II


如有任何问题或建议,欢迎留言讨论!

相关文章
|
算法 C++ Python
每日算法系列【LeetCode 685】冗余连接 II
每日算法系列【LeetCode 685】冗余连接 II
|
算法 C++ Python
每日算法系列【LeetCode 684】冗余连接
每日算法系列【LeetCode 684】冗余连接
leetcode 685 冗余连接II
leetcode 685 冗余连接II
87 0
leetcode 685 冗余连接II
|
算法
【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]
学习LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]。
116 0
【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]
Leetcode | 连接两字母单词得到的最长回文串
Leetcode | 连接两字母单词得到的最长回文串
143 0
Leetcode | 连接两字母单词得到的最长回文串
【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
学习了解[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]。
94 0
【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
LeetCode每日一题——1640. 能否连接形成数组
如果可以连接 pieces 中的数组形成 arr ,返回 true ;否则,返回 false 。
75 0
|
机器学习/深度学习 自然语言处理 算法
每日算法系列【LeetCode 685】冗余连接 II
在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。
129 0
每日算法系列【LeetCode 685】冗余连接 II
|
算法 容器
[leetcode] 连接所有点的最小费用 -MST
这道题是最小生成树板子题 可以用并查集实现,贪心排序边权 讲一个二元组放在一个vector容器里面,其中的元素为<weight,<u,v>>对应<int,<int,int> >类型,第一个参数代表边权的大小,后面的为两个点u,v,然后按照第一个值边权从小到大排序,然后用并查集实现是否连通,从而实现最小生成树 代码有点套娃(
105 0
[leetcode] 连接所有点的最小费用 -MST