力扣-重新规划路线

思路分析

1. 预处理：构建带 “反转标记” 的邻接表（最核心的优化点）
   传统思路是用 “无向邻接表 + 哈希集合存原始边”，而这段代码直接在邻接表中存储边的方向和反转代价：
   对于原始有向边 a->b：
   向 a 的邻接列表中添加 {b, 1}：表示从 a 到 b 是原始方向，若遍历路径是 a→b（背离 0），则需要反转这条边，标记代价 1；
   向 b 的邻接列表中添加 {a, 0}：表示从 b 到 a 是反向方向，若遍历路径是 b→a（指向 0），则无需反转，标记代价 0。
   这种设计的本质：把 “判断原始边方向” 和 “统计反转数” 合并到邻接表中，无需额外存储和查询原始边，空间和时间效率更高。
2. BFS 初始化
   队列：存储待遍历的城市，初始放入起点城市 0（BFS 的层序遍历起点）；
   访问数组：标记已遍历的城市，避免重复处理（比如 0→1 后，不再处理 1→0）；
   结果计数器 res：初始为 0，累计需要反转的边数。
3. BFS 核心遍历逻辑
   取出队列头部的当前城市 curr；
   遍历 curr 的所有邻接节点（每个邻接节点是 {next, flag} 数组）：
   若 next 未被访问：
   ✅ 累加 flag 到 res（flag=1 则反转，flag=0 则不反转）；
   ✅ 标记 next 为已访问；
   ✅ 将 next 加入队列，继续下一层遍历；
   若 next 已被访问：跳过（避免回头遍历）。
   队列为空时，res 就是需要反转的最小边数。

代码实现

publicintminReorder(intn,int[][]connections){// 1. 构建邻接表：adj[x] = {{y, flag}, ...}List<List<int[]>>adj=newArrayList<>();for(inti=0;i<n;i++){adj.add(newArrayList<>());}for(int[]conn:connections){inta=conn[0],b=conn[1];adj.get(a).add(newint[]{b,1});// a→b 是原始边，需反转则+1，标记flag=1adj.get(b).add(newint[]{a,0});// b→a 是反向边，无需反转，标记flag=0}// 2. BFS初始化：队列+访问数组，从0出发Queue<Integer>queue=newLinkedList<>();boolean[]visited=newboolean[n];queue.offer(0);visited[0]=true;intres=0;// 记录需要反转的边数// 3. BFS遍历while(!queue.isEmpty()){intcurr=queue.poll();// 遍历当前节点的所有邻接节点for(int[]neighbor:adj.get(curr)){intnext=neighbor[0];intflag=neighbor[1];if(!visited[next]){// 未访问过的节点才处理res+=flag;// flag=1则反转，计数+1；flag=0无操作visited[next]=true;queue.offer(next);}}}returnres;}

复杂度分析

• 时间 O (n)（每个节点 / 边仅遍历一次），
• 空间 O (n)（邻接表 + 队列 + 访问数组），