给定一棵树的头节点head，原本是一棵正常的树，
现在，在树上多加了一条冗余的边，
请找到这条冗余的边并返回。
1.指向头，入度没有0的。入度没有2的。
2.未指向头，某一个点入度一定是2。
2.1.左右双全是父节点，另一个不全的不是父节点。
2.2.如果都不全，任选一个。
并查集。如果边两边的点在同一个集合，说明是冗余的。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
edges := [][]int{{1, 2}, {1, 3}, {2, 3}}
ret := findRedundantDirectedConnection(edges)
fmt.Println(ret)
}
func findRedundantDirectedConnection(edges [][]int) []int {
// N是点的数量
// 点的编号，1~N，没有0
N := len(edges)
// 并查集！N个点，去初始化，每个点各自是一个集合
uf := NewUnionFind(N)
// pre[i] = 0 来到i节点是第一次
// pre[i] = 6 之前来过i，是从6来的！
pre := make([]int, N+1)
// 如果，没有入度为2的点，
// first second 都维持是null
// 如果，有入度为2的点，那么也只可能有一个
// 比如入度为2的点，是5
// first = [3,5]
// second = [12,5]
var first []int
var second []int
// 有没有环！非常不单纯！含义复杂！
var circle []int
for i := 0; i < N; i++ { // 遍历每条边！
from := edges[i][0]
to := edges[i][1]
if pre[to] != 0 { // 不止一次来过to！
first = []int{pre[to], to}
second = edges[i]
} else { // 第一次到达to，
pre[to] = from
if uf.same(from, to) {
circle = edges[i]
} else {
uf.union(from, to)
}
}
}
// 重点解析！这是啥？？？
// first != null
// 有入度为2的点！
return twoSelectOne(first != nil, twoSelectOne(circle != nil, first, second), circle)
}
func twoSelectOne(c bool, a, b []int) []int {
if c {
return a
} else {
return b
}
}
type UnionFind struct {
f []int
s []int
h []int
}
func NewUnionFind(N int) *UnionFind {
ans := &UnionFind{}
ans.f = make([]int, N+1)
ans.s = make([]int, N+1)
ans.h = make([]int, N+1)
for i := 0; i <= N; i++ {
ans.f[i] = i
ans.s[i] = 1
}
return ans
}
func (this *UnionFind) find(i int) int {
hi := 0
for i != this.f[i] {
this.h[hi] = i
hi++
i = this.f[i]
}
for hi > 0 {
hi--
this.f[this.h[hi]] = i
}
return i
}
func (this *UnionFind) same(i, j int) bool {
return this.find(i) == this.find(j)
}
func (this *UnionFind) union(i, j int) {
fi := this.find(i)
fj := this.find(j)
if fi != fj {
if this.s[fi] >= this.s[fj] {
this.f[fj] = fi
this.s[fi] = this.s[fi] + this.s[fj]
} else {
this.f[fi] = fj
this.s[fj] = this.s[fi] + this.s[fj]
}
}
}执行结果如下：
