684. Redundant Connection
思路:
记录每点出现在edges的次数
把出现1次的点抓出来丢到queue里
接着从queue里面抓点出来
并且扣掉跟他相连的点的次数
扣到剩1次后就丢到queue里面
重复这个动作
最后只有组成cycle的点次数会是2
其他都会<=1
接着就从edges后面开始往回找，只要edges的两点出现次数都是2
那就回传该edge
golang code :
func findRedundantConnection(edges [][]int) []int {
n := len(edges)
path, degree := make([][]int, n+1), make([]int, n+1)
for _, val := range edges {
degree[val[1]]++
degree[val[0]]++
path[val[0]] = append(path[val[0]], val[1])
path[val[1]] = append(path[val[1]], val[0])
}
queue := []int{}
for key, val := range degree {
if val == 1 {
queue = append(queue, key)
}
}
for len(queue) > 0 {
curNode := queue[0]
queue = queue[1:]
for _, val := range path[curNode] {
degree[val]