力扣刷题记录
并查集 有向图
685. 冗余连接 II
思路
对于这道困难题，并没有思路
从昨天的无向图变为今天的有向图，题目从中等升级到了困难
因此需要同时记录上一级连接的节点和使用并查集
树中所有入度除了一个为0 其它的为1
记录上一级的节点是为了判断是否存在冲突的边，即这个点存在两个入度
因此记录这一条冲突的边
否则判断这条边是否会形成环路
通过加入并查集 进行判断 成环了 记录下来
最后如果没有冲突的边 跟昨天一样 返回最后标记成环的边即可
否则
有冲突的边 假设为 [u, v] 此时肯定得返回 [u, v] 或者 [parents[v], v] 中的一条（为了保证入度正常）
没有成环的边 返回冲突的边 [u, v]即可
如果既有冲突的边， 也有成环的边，成环的边不可能是[u, v] 因为已经被标记了，不会进入成环的监测再进行标记， 因此直接 返回 另外一条边 [parents[v], v] 即可 （不一定返回最后标记的成环那一条边，因为一个环中的另外一条边[parents[v], v] 需要返回 才能同时去掉环和存在入度异常的点）
代码
func find(ancestor []int, x int) int{if ancestor[x] != x{ancestor[x] = find(ancestor, ancestor[x]) // 路径压缩 只保留最根的节点// return find(ancestor, ancestor[x]) // 不进行路径压缩}return ancestor[x]
}func findRedundantDirectedConnection(edges [][]int) []int {var parents []int = make([]int, len(edges) + 1) // 记录上一级父节点var ancestor []int = make([]int, len(edges) + 1) // 记录最上面的祖先节点 并查集for i := 0; i < len(edges) + 1 ; i++{parents[i] = iancestor[i] = i}conflict := -1cycle := -1for i, edge := range edges{from := edge[0]to := edge[1]if parents[to] != to{// 该点 已经在一条边中加入了 已经有一个入度了conflict = i}else{parents[to] = fromm := find(ancestor, from)n := find(ancestor, to)if m == n{// 成环了cycle = i}else{ancestor[m] = n}}}if conflict < 0{// 和昨天的一样，返回成环的边即可return edges[cycle]}else{to := edges[conflict][1]if cycle >= 0{var res []int = make([]int, 2)res[0] = parents[to]res[1] = toreturn res}else{// 没有成环的 返回 冲突的边即可return edges[conflict]}}
}
时间复杂度：O(n*logn)
空间复杂度：O(n)