网络异常,图片无法展示
|
在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。
输入一个有向图,该图由一个有着 n
个节点(节点值不重复,从 1
到 n
)的树及一条附加的有向边构成。附加的边包含在 1
到 n
中的两个不同顶点间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges
。 每个元素是一对 [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
解题思路
本题依然是一个连通性问题,只不过在连通性的基础上添加了有向性,使问题变得更复杂了。
本题中有向图的连接方式可以分为三种类型,要根据连接方式分类讨论其返回值。
- 示例1 中的连接情况,有一个子节点有两个父节点,定义为双入度情况
- 示例2 中的连接情况,连接形成了环,定义为成环情况
- 示例中未给出的情况,即成环,又有双入度的情况
针对双入度的情况,需要返回的边是形成双入度的边。
针对成环的情况,需要返回的边是成环的边。
针对即成环,又有双入度的情况,需要返回的是双入度边的子节点及其父节点组成的边。
动画演示
网络异常,图片无法展示
|
代码实现
// 并查集 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
如有任何问题或建议,欢迎留言讨论!