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]