LCP 21. 追逐游戏 - Rust 实现题目概述给定 N 个景点、N 条小路构成的无向连通图即基环树一棵树加一条边形成唯一环。小力A和小扣B分别从 startA、startB 出发每回合 A 先移动B 后移动均可选择移动到相邻点或留在原地。求 A 抓到 B 的最少回合数若无法抓到返回 -1。---核心思路关键性质N 点 N 边连通图 有且仅有一个环。分情况讨论情况 条件 结果A、B 相邻 存在边直接连接 返回 1A 第一回合直接走到 B环长度 3 且 B 能先到达环 环上存在点 i 满足 da[i] db[i] 1 返回 -1B 在环上与 A 二人转永远逃脱环长度 3 三角环上 B 无处可逃 A 一定能抓到其他 — 答案 \max\{ da[i] \mid da[i] db[i] 1 \}其中 da[i]、db[i] 分别为 A、B 到点 i 的最短距离。条件 da[i] db[i] 1 表示 B 能比 A 早至少 2 步到达点 i该点对 B 是安全的。B 会选择安全点中 A 距离最远的点以最大化回合数。算法步骤1. 建图 判断 A、B 是否相邻2. BFS 求 A、B 到所有点的最短距离3. 拓扑排序剥叶子找环不断将度为 1 的节点删除剩下的即为环上节点4. 按上述规则分情况输出---Rust 代码rustuse std::collections::VecDeque;impl Solution {pub fn chase_game(edges: VecVeci32, start_a: i32, start_b: i32) - i32 {let n edges.len();// 转为 0-basedlet start_a (start_a - 1) as usize;let start_b (start_b - 1) as usize;let mut g vec![vec![]; n];let mut deg vec![0; n];let mut adjacent false;for e in edges {let u (e[0] - 1) as usize;let v (e[1] - 1) as usize;if (u start_a v start_b) || (u start_b v start_a) {adjacent true;}g[u].push(v);g[v].push(u);deg[u] 1;deg[v] 1;}// 情况 1A、B 相邻第一回合直接抓到if adjacent {return 1;}// BFS 求单源最短距离let bfs |src: usize| - Veci32 {let mut dis vec![-1; n];let mut q VecDeque::new();dis[src] 0;q.push_back(src);while let Some(u) q.pop_front() {for v in g[u] {if dis[v] -1 {dis[v] dis[u] 1;q.push_back(v);}}}dis};let da bfs(start_a);let db bfs(start_b);// 拓扑排序剥叶子找环上节点let mut deg2 deg.clone();let mut q VecDeque::new();let mut in_cycle vec![true; n];for i in 0..n {if deg2[i] 1 {q.push_back(i);}}while let Some(u) q.pop_front() {in_cycle[u] false;for v in g[u] {if in_cycle[v] {deg2[v] - 1;if deg2[v] 1 {q.push_back(v);}}}}let cycle_len in_cycle.iter().filter(|x| x).count();// 情况 2环长度 3且 B 能先于 A 到达环上某点距离差 2if cycle_len 3 {for i in 0..n {if in_cycle[i] da[i] db[i] 1 {return -1;}}}// 情况 3A 能追到 B答案为 B 能安全到达的最远点let mut ans 1;for i in 0..n {if da[i] db[i] 1 {ans ans.max(da[i]);}}ans}}---复杂度分析指标 复杂度 说明时间 O(N) 建图 O(N) 两次 BFS O(N) 拓扑排序 O(N)空间 O(N) 邻接表、距离数组、队列等
Kimi LeetCode LCP 21. 追逐游戏 Rust实现
LCP 21. 追逐游戏 - Rust 实现题目概述给定 N 个景点、N 条小路构成的无向连通图即基环树一棵树加一条边形成唯一环。小力A和小扣B分别从 startA、startB 出发每回合 A 先移动B 后移动均可选择移动到相邻点或留在原地。求 A 抓到 B 的最少回合数若无法抓到返回 -1。---核心思路关键性质N 点 N 边连通图 有且仅有一个环。分情况讨论情况 条件 结果A、B 相邻 存在边直接连接 返回 1A 第一回合直接走到 B环长度 3 且 B 能先到达环 环上存在点 i 满足 da[i] db[i] 1 返回 -1B 在环上与 A 二人转永远逃脱环长度 3 三角环上 B 无处可逃 A 一定能抓到其他 — 答案 \max\{ da[i] \mid da[i] db[i] 1 \}其中 da[i]、db[i] 分别为 A、B 到点 i 的最短距离。条件 da[i] db[i] 1 表示 B 能比 A 早至少 2 步到达点 i该点对 B 是安全的。B 会选择安全点中 A 距离最远的点以最大化回合数。算法步骤1. 建图 判断 A、B 是否相邻2. BFS 求 A、B 到所有点的最短距离3. 拓扑排序剥叶子找环不断将度为 1 的节点删除剩下的即为环上节点4. 按上述规则分情况输出---Rust 代码rustuse std::collections::VecDeque;impl Solution {pub fn chase_game(edges: VecVeci32, start_a: i32, start_b: i32) - i32 {let n edges.len();// 转为 0-basedlet start_a (start_a - 1) as usize;let start_b (start_b - 1) as usize;let mut g vec![vec![]; n];let mut deg vec![0; n];let mut adjacent false;for e in edges {let u (e[0] - 1) as usize;let v (e[1] - 1) as usize;if (u start_a v start_b) || (u start_b v start_a) {adjacent true;}g[u].push(v);g[v].push(u);deg[u] 1;deg[v] 1;}// 情况 1A、B 相邻第一回合直接抓到if adjacent {return 1;}// BFS 求单源最短距离let bfs |src: usize| - Veci32 {let mut dis vec![-1; n];let mut q VecDeque::new();dis[src] 0;q.push_back(src);while let Some(u) q.pop_front() {for v in g[u] {if dis[v] -1 {dis[v] dis[u] 1;q.push_back(v);}}}dis};let da bfs(start_a);let db bfs(start_b);// 拓扑排序剥叶子找环上节点let mut deg2 deg.clone();let mut q VecDeque::new();let mut in_cycle vec![true; n];for i in 0..n {if deg2[i] 1 {q.push_back(i);}}while let Some(u) q.pop_front() {in_cycle[u] false;for v in g[u] {if in_cycle[v] {deg2[v] - 1;if deg2[v] 1 {q.push_back(v);}}}}let cycle_len in_cycle.iter().filter(|x| x).count();// 情况 2环长度 3且 B 能先于 A 到达环上某点距离差 2if cycle_len 3 {for i in 0..n {if in_cycle[i] da[i] db[i] 1 {return -1;}}}// 情况 3A 能追到 B答案为 B 能安全到达的最远点let mut ans 1;for i in 0..n {if da[i] db[i] 1 {ans ans.max(da[i]);}}ans}}---复杂度分析指标 复杂度 说明时间 O(N) 建图 O(N) 两次 BFS O(N) 拓扑排序 O(N)空间 O(N) 邻接表、距离数组、队列等