以下是 LeetCode LCP 21. 追逐游戏的 Java 实现基于 BFS 拓扑排序找环的经典解法javaclass Solution {private ListListInteger 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);QueueInteger 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);QueueInteger 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)
Kimi LeetCode LCP 21. 追逐游戏 Java实现
以下是 LeetCode LCP 21. 追逐游戏的 Java 实现基于 BFS 拓扑排序找环的经典解法javaclass Solution {private ListListInteger 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);QueueInteger 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);QueueInteger 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)
