网站中文章内图片做超链接,响应式h5网站多少钱,做寄生虫对自己的网站有影响吗,辽宁沈阳建设工程信息网思路分析 预处理#xff1a;构建带 “反转标记” 的邻接表#xff08;最核心的优化点#xff09; 传统思路是用 “无向邻接表 哈希集合存原始边”#xff0c;而这段代码直接在邻接表中存储边的方向和反转代价#xff1a; 对于原始有向边 a-b#xff1a; 向 a 的邻接…思路分析预处理构建带 “反转标记” 的邻接表最核心的优化点传统思路是用 “无向邻接表 哈希集合存原始边”而这段代码直接在邻接表中存储边的方向和反转代价对于原始有向边 a-b向 a 的邻接列表中添加 {b, 1}表示从 a 到 b 是原始方向若遍历路径是 a→b背离 0则需要反转这条边标记代价 1向 b 的邻接列表中添加 {a, 0}表示从 b 到 a 是反向方向若遍历路径是 b→a指向 0则无需反转标记代价 0。这种设计的本质把 “判断原始边方向” 和 “统计反转数” 合并到邻接表中无需额外存储和查询原始边空间和时间效率更高。BFS 初始化队列存储待遍历的城市初始放入起点城市 0BFS 的层序遍历起点访问数组标记已遍历的城市避免重复处理比如 0→1 后不再处理 1→0结果计数器 res初始为 0累计需要反转的边数。BFS 核心遍历逻辑取出队列头部的当前城市 curr遍历 curr 的所有邻接节点每个邻接节点是 {next, flag} 数组若 next 未被访问✅ 累加 flag 到 resflag1 则反转flag0 则不反转✅ 标记 next 为已访问✅ 将 next 加入队列继续下一层遍历若 next 已被访问跳过避免回头遍历。队列为空时res 就是需要反转的最小边数。代码实现publicintminReorder(intn,int[][]connections){// 1. 构建邻接表adj[x] {{y, flag}, ...}ListListint[]adjnewArrayList();for(inti0;in;i){adj.add(newArrayList());}for(int[]conn:connections){intaconn[0],bconn[1];adj.get(a).add(newint[]{b,1});// a→b 是原始边需反转则1标记flag1adj.get(b).add(newint[]{a,0});// b→a 是反向边无需反转标记flag0}// 2. BFS初始化队列访问数组从0出发QueueIntegerqueuenewLinkedList();boolean[]visitednewboolean[n];queue.offer(0);visited[0]true;intres0;// 记录需要反转的边数// 3. BFS遍历while(!queue.isEmpty()){intcurrqueue.poll();// 遍历当前节点的所有邻接节点for(int[]neighbor:adj.get(curr)){intnextneighbor[0];intflagneighbor[1];if(!visited[next]){// 未访问过的节点才处理resflag;// flag1则反转计数1flag0无操作visited[next]true;queue.offer(next);}}}returnres;}复杂度分析时间 O (n)每个节点 / 边仅遍历一次空间 O (n)邻接表 队列 访问数组