做公众号策划的网站,徐州建设工程招投标官方网站,视频网站建站程序,泰州市建设局网站【LetMeFly】685.冗余连接 II#xff1a;并查集#xff08;和I有何不同分析#xff09;——详细题解(附图)
力扣题目链接#xff1a;https://leetcode.cn/problems/redundant-connection-ii/
在本问题中#xff0c;有根树指满足以下条件的 有向 图。该树只有一个根节点并查集和I有何不同分析——详细题解(附图)
力扣题目链接https://leetcode.cn/problems/redundant-connection-ii/
在本问题中有根树指满足以下条件的 有向 图。该树只有一个根节点所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点而根节点没有父节点。
输入一个有向图该图由一个有着 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.length3 n 1000edges[i].length 21 ui, vi n
解题方法并查集 解题思路
这题和684.冗余连接的区别是 684的无向图只需要考虑有没有形成自环而本题有向图还需要考虑“是否形成了入度为2的节点”。 如果形成了“入度为2”的节点例如下面两种情况在684.冗余连接中只需要移除“首次形成(无向)环”的边而在685.冗余连接II中就不能只移除“最后出现的导致形成(无向)环的边” 1-----2 1------
↑ ↑ ↑ ↓
3------ 2-----3---4左图中只能移除[1,2]或[3,2]而不能移除[3,1]右图中只能移除[1,3]而不能移除[3,2]或[2,1]。 有向边不能和无向边一概而论的本质原因是树中一个节点不能有两个父节点即入度不能为2。所以一旦出现了入度为2的节点 n o d e node node就要在“终点为 n o d e node node的两条边”里面选择一条移除。判断方法如下 尝试移除一条边判断剩下的边不考虑方向能否构成无向环如果不构成无向环则说明这条边可以被移除。 判断方法就和684题一模一样了使用并查集即可完成判断。 树上多一条边就一定存在入度为2的节点吗不一定还可能有以下这种情况 1------
↑ ↓
2-----3-----4图中节点[1,2,3]形成了一个环但1、2、3、44个节点的入度都为1。 这样就和684题一模一样了其实在环[1,2,3]里任意移除一条边图都能变成树。 同样使用并查集返回第一条“形成环”的边即为所求。 解题方法
首先统计是否有入度为2的节点
若有则尝试移除指向2的边若移除后图中无环则这条边可以被移除否则移除第一条导致“环出现”的边
常见问题回答QA
Q1 若有入度为2的节点在判断“移除一条边后图是否为树”时能否通过“统计每个点是否孤立(入度出度都为0)”来判断
例如下图中终点为3的边有[1,3]和[4,3]两条移除[4,3]的话会导致点4成为孤立点因此只能移除[1,3]。
1------
↑ ↓
2-----3---4A1 不能这么判断。例如下图只能移除[2,4]不能移除[5,2]但其实移除其中的任意一条都不会产生“孤立点”。
---
↓ ↑
4--2↑
1--5--3建议修改为“通过判断图是否联通”的方式判断某条边是否可以移除。
时空复杂度
时间复杂度最坏 O ( n log n ) O(n\log n) O(nlogn)平均为 O ( n α ( n ) ) O(n\alpha(n)) O(nα(n))接近 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
AC代码
C
class Solution {
private:vectorint fa;bool couldRemoveThisEdge(vectorvectorint edges, int index) {initFa(edges.size());for (int i 0; i edges.size(); i) {if (i index) {continue;}if (find(edges[i][0]) find(edges[i][1])) {return false;}union_(edges[i][0], edges[i][1]);}return true;}vectorint solution_indegree(vectorvectorint edges, int node) {for (int i edges.size() - 1; i 0; i--) {if (edges[i][1] node couldRemoveThisEdge(edges, i)) {return edges[i];}}return {}; // FAKE RETURN}int find(int x) {if (x ! fa[x]) {fa[x] find(fa[x]);}return fa[x];}void union_(int x, int y) {fa[find(x)] find(y);}void initFa(int n) {fa.resize(n 1);for (int i 1; i n; i) {fa[i] i;}}vectorint solution_unionFind(vectorvectorint edges) {initFa(edges.size());for (vectorint edge : edges) {if (find(edge[0]) find(edge[1])) {return edge;} else {union_(edge[0], edge[1]);}}return {}; // FAKE RETURN}
public:vectorint findRedundantDirectedConnection(vectorvectorint edges) {vectorbool inDegree(edges.size() 1);for (vectorint edge : edges) {if (inDegree[edge[1]]) { // 找到了入度为2的点return solution_indegree(edges, edge[1]);} else {inDegree[edge[1]] true;}}return solution_unionFind(edges);}
};Python
from typing import Listclass Solution:def initFa(self) - None:for i in range(1, len(self.edges) 1):self.fa[i] idef find(self, x: int) - int:if self.fa[x] ! x:self.fa[x] self.find(self.fa[x])return self.fa[x]def union(self, x: int, y: int) - None:self.fa[self.find(x)] self.find(y)def couldRemoveThisEdge(self, index: int) - bool:self.initFa()for i in range(len(self.edges)):if i index:continueif self.find(self.edges[i][0]) self.find(self.edges[i][1]):return Falseelse:self.union(self.edges[i][0], self.edges[i][1])return Truedef solution_indegree(self, node: int) - List[int]:for i in range(len(self.edges) - 1, -1, -1):if self.edges[i][1] node and self.couldRemoveThisEdge(i):return self.edges[i]return [] # FAKE RETURNdef solution_unionFind(self) - List[int]:self.initFa()for x, y in self.edges:if self.find(x) self.find(y):return [x, y]else:self.union(x, y)return [] # FAKE RETURNdef findRedundantDirectedConnection(self, edges: List[List[int]]) - List[int]:self.fa [0] * (len(edges) 1)self.edges edgeshasIndegree [False] * (len(edges) 1)for x, y in edges:if hasIndegree[y]:return self.solution_indegree(y)else:hasIndegree[y] Truereturn self.solution_unionFind()Java
class UnionFind {private int[] fa;public UnionFind(int n) {fa new int[n 1];for (int i 1; i n; i) {fa[i] i;}}private int find(int x) {if (fa[x] ! x) {fa[x] find(fa[x]);}return fa[x];}public boolean isUnion(int x, int y) {return find(x) find(y);}public void union(int x, int y) {fa[find(x)] find(y);}
}class Solution {private boolean canRemoveThisEdge(int[][] edges, int index) {UnionFind unionFind new UnionFind(edges.length);for (int i 0; i edges.length; i) {if (i index) {continue;}if (unionFind.isUnion(edges[i][0], edges[i][1])) {return false;} else {unionFind.union(edges[i][0], edges[i][1]);}}return true;}private int[] solution_indegree(int[][] edges, int node) {for (int i edges.length - 1; i 0; i--) {if (edges[i][1] node canRemoveThisEdge(edges, i)) {return edges[i];}}return new int[0]; // FAKE RETURN}private int[] solution_unionFind(int[][] edges) {UnionFind unionFind new UnionFind(edges.length);for (int[] edge : edges) {if (unionFind.isUnion(edge[0], edge[1])) {return edge;} else {unionFind.union(edge[0], edge[1]);}}return new int[0]; // FAKE RETURN}public int[] findRedundantDirectedConnection(int[][] edges) {boolean[] hasIndegree new boolean[edges.length 1];for (int[] edge : edges) {if (hasIndegree[edge[1]]) {return solution_indegree(edges, edge[1]);} else {hasIndegree[edge[1]] true;}}return solution_unionFind(edges);}
}Go
package maintype UnionFind struct {fa []int
}func New(n int) UnionFind {fa : make([]int, n 1)for th, _ : range fa {fa[th] th}return UnionFind{fa}
}func (unionFind UnionFind) _find(x int) int {if unionFind.fa[x] ! x {unionFind.fa[x] unionFind._find(unionFind.fa[x])}return unionFind.fa[x]
}func (unionFind UnionFind) isUnion(x, y int) bool {return unionFind._find(x) unionFind._find(y)
}func (unionFind UnionFind) union(x, y int) {unionFind.fa[unionFind._find(x)] unionFind._find(y)
}func canRemoveThisEdge(edges [][]int, index int) bool {unionFind : New(len(edges))for i : 0; i len(edges); i {if i index {continue}if unionFind.isUnion(edges[i][0], edges[i][1]) {return false} else {unionFind.union(edges[i][0], edges[i][1])}}return true
}func solution_indegree(edges [][]int, node int) []int {for i : len(edges) - 1; i 0; i-- {if edges[i][1] node canRemoveThisEdge(edges, i) {return edges[i]}}return make([]int, 0) // FAKE RETURN
}func solution_unionFind(edges [][]int) []int {unionFind : New(len(edges))for _, edge : range edges {if unionFind.isUnion(edge[0], edge[1]) {return edge} else {unionFind.union(edge[0], edge[1])}}return make([]int, 0) // FAKE RETURN
}func findRedundantDirectedConnection(edges [][]int) []int {hasIndegree : make([]bool, len(edges) 1)for _, edge : range edges {if hasIndegree[edge[1]] {return solution_indegree(edges, edge[1])} else {hasIndegree[edge[1]] true}}return solution_unionFind(edges)
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/143470538
