企业官网建设流程全解析

LCP 21. 追逐游戏 - Golang 实现

沿用上一问的核心思路（基环树 + BFS + 拓扑剥叶子），直接给出 Golang 实现：

```go
func chaseGame(edges [][]int, startA int, startB int) int {
n := len(edges)
// 转为 0-based
a, b := startA-1, startB-1

g := make([][]int, n)
deg := make([]int, n)
adjacent := false

for _, e := range edges {
u, v := e[0]-1, e[1]-1
if (u == a && v == b) || (u == b && v == a) {
adjacent = true
}
g[u] = append(g[u], v)
g[v] = append(g[v], u)
deg[u]++
deg[v]++
}

// 情况 1：A、B 相邻，第一回合直接抓到
if adjacent {
return 1
}

// BFS 求单源最短距离
bfs := func(src int) []int {
dis := make([]int, n)
for i := range dis {
dis[i] = -1
}
q := make([]int, 0, n)
dis[src] = 0
q = append(q, src)
for head := 0; head < len(q); head++ {
u := q[head]
for _, v := range g[u] {
if dis[v] == -1 {
dis[v] = dis[u] + 1
q = append(q, v)
}
}
}
return dis
}

da := bfs(a)
db := bfs(b)

// 拓扑排序（剥叶子）找环上节点
deg2 := make([]int, n)
copy(deg2, deg)
inCycle := make([]bool, n)
for i := range inCycle {
inCycle[i] = true
}

q := make([]int, 0, n)
for i := 0; i < n; i++ {
if deg2[i] == 1 {
q = append(q, i)
}
}
for head := 0; head < len(q); head++ {
u := q[head]
inCycle[u] = false
for _, v := range g[u] {
if inCycle[v] {
deg2[v]--
if deg2[v] == 1 {
q = append(q, v)
}
}
}
}

cycleLen := 0
for _, v := range inCycle {
if v {
cycleLen++
}
}

// 情况 2：环长度 > 3，且 B 能先于 A 到达环上某点（距离差 >= 2）
if cycleLen > 3 {
for i := 0; i < n; i++ {
if inCycle[i] && da[i] > db[i]+1 {
return -1
}
}
}

// 情况 3：A 能追到 B，答案为 B 能安全到达的最远点
ans := 1
for i := 0; i < n; i++ {
if da[i] > db[i]+1 && da[i] > ans {
ans = da[i]
}
}

return ans
}
```

---

复杂度分析

指标 复杂度 说明
时间 O(N) 建图 + 两次 BFS + 拓扑排序各 O(N)
空间 O(N) 邻接表、距离数组、队列等