-
-
Notifications
You must be signed in to change notification settings - Fork 5.7k
/
685. Redundant Connection II.go
44 lines (42 loc) · 1.49 KB
/
685. Redundant Connection II.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package leetcode
func findRedundantDirectedConnection(edges [][]int) []int {
if len(edges) == 0 {
return []int{}
}
parent, candidate1, candidate2 := make([]int, len(edges)+1), []int{}, []int{}
for _, edge := range edges {
if parent[edge[1]] == 0 {
parent[edge[1]] = edge[0]
} else { // 如果一个节点已经有父亲节点了,说明入度已经有 1 了,再来一条边,入度为 2 ,那么跳过新来的这条边 candidate2,并记录下和这条边冲突的边 candidate1
candidate1 = append(candidate1, parent[edge[1]])
candidate1 = append(candidate1, edge[1])
candidate2 = append(candidate2, edge[0])
candidate2 = append(candidate2, edge[1])
edge[1] = 0 // 做标记,后面再扫到这条边以后可以直接跳过
}
}
for i := 1; i <= len(edges); i++ {
parent[i] = i
}
for _, edge := range edges {
if edge[1] == 0 { // 跳过 candidate2 这条边
continue
}
u, v := edge[0], edge[1]
pu := findRoot(&parent, u)
if pu == v { // 发现有环
if len(candidate1) == 0 { // 如果没有出现入度为 2 的情况,那么对应情况 1,就删除这条边
return edge
}
return candidate1 // 出现环并且有入度为 2 的情况,说明 candidate1 是答案
}
parent[v] = pu // 没有发现环,继续合并
}
return candidate2 // 当最后什么都没有发生,则 candidate2 是答案
}
func findRoot(parent *[]int, k int) int {
if (*parent)[k] != k {
(*parent)[k] = findRoot(parent, (*parent)[k])
}
return (*parent)[k]
}