企业官网建设流程全解析

以下是 LeetCode LCP 21. 追逐游戏的 Java 实现，基于 BFS + 拓扑排序找环的经典解法：

```java
class Solution {
private List<List<Integer>> g;

public int chaseGame(int[][] edges, int startA, int startB) {
int n = edges.length;
g = new ArrayList<>();
for (int i = 0; i < n; i++) {
g.add(new ArrayList<>());
}

int[] degree = new int[n];
for (int[] e : edges) {
int u = e[0] - 1, v = e[1] - 1;
// 特判：A和B相邻，第一回合直接抓到
if ((u == startA - 1 && v == startB - 1) ||
(u == startB - 1 && v == startA - 1)) {
return 1;
}
g.get(u).add(v);
g.get(v).add(u);
degree[u]++;
degree[v]++;
}

startA--;
startB--;

// BFS求A、B到各点的最短距离
int[] da = bfs(startA);
int[] db = bfs(startB);

// 拓扑排序找环（基环树：N个点N条边，去掉所有叶子后剩余的就是环）
boolean[] inLoop = new boolean[n];
Arrays.fill(inLoop, true);
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
q.add(i);
}
}
while (!q.isEmpty()) {
int u = q.poll();
inLoop[u] = false;
for (int v : g.get(u)) {
degree[v]--;
if (degree[v] == 1) {
q.add(v);
}
}
}

// 统计环的长度
int loopLen = 0;
for (int i = 0; i < n; i++) {
if (inLoop[i]) loopLen++;
}

// 判断B能否逃脱：若环长度>3，且存在环上点i满足 da[i] > db[i] + 1
// 说明B能先到达环上某点，且A无法拦截，B可在环上永远绕圈
if (loopLen > 3) {
for (int i = 0; i < n; i++) {
if (inLoop[i] && da[i] > db[i] + 1) {
return -1;
}
}
}

// 若A能追到B，答案为所有满足 da[i] > db[i] + 1 的点中 da[i] 的最大值
// 因为B会选择一个A到达时间比B到达时间至少多2的点，尽可能拖延
int ans = 0;
for (int i = 0; i < n; i++) {
if (da[i] > db[i] + 1) {
ans = Math.max(ans, da[i]);
}
}

return ans;
}

private int[] bfs(int start) {
int n = g.size();
int[] dis = new int[n];
Arrays.fill(dis, -1);
Queue<Integer> q = new LinkedList<>();
q.add(start);
dis[start] = 0;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g.get(u)) {
if (dis[v] == -1) {
dis[v] = dis[u] + 1;
q.add(v);
}
}
}
return dis;
}
}
```

核心思路

1. 图结构分析：题目给的是 N 个点 N 条边的连通图，即基环树（一棵树 + 一条边形成环）

2. 找环：用类似拓扑排序的方法，不断删除度为 1 的叶子节点，最后剩下的就是环上的点

3. BFS 求距离：分别计算 A 和 B 到所有点的最短距离 `da[]` 和 `db[]`

4. 判断逃脱条件：
- 若环长度 > 3，且存在环上点满足 `da[i] > db[i] + 1`，则 B 能先上环并永远绕圈，返回 `-1`
- 若环长度 = 3，即使 B 上了环，A 也能在有限步内抓到 B（因为三角形环上无处可逃）

5. 计算答案：A 能追到 B 时，B 会选择一个满足 `da[i] > db[i] + 1` 的点尽可能拖延，答案就是这些点中 `da[i]` 的最大值

复杂度

- 时间复杂度：O(N)
- 空间复杂度：O(N)