目录1. 核心超时原因2. 正确建图思路优化后完整代码DFS 版AC 不超时关键优化点对比旧代码缺陷新版优化点补充BFS 迭代版防止递归深度过大栈溢出原理简单说明1. 核心超时原因双重循环 O (n²)dfs 里写了for(int i 0; i n; i)每次遍历全部 n 个节点n 大时直接爆炸。List.contains () 是 O (k) 线性查找graph.get(pos).contains(i)每次遍历邻接表双重嵌套复杂度极高。图只存单向边没有标记原道路方向原数组connections[a,b]代表原生道路 a→b需要反转而 b→a 是虚拟反向边不用反转。你现在单纯存单向列表判断是否要翻转的逻辑低效且容易出错。2. 正确建图思路每条道路[u, v]u → v真实道路走到这里需要翻转标记权重1v → u虚拟反向通路不用翻转标记权重0邻接表存(邻接点, 是否需要翻转)一次遍历就能拿到所有邻居不用循环全部节点。优化后完整代码DFS 版AC 不超时import java.util.ArrayList; import java.util.List; class Solution { int res 0; public int minReorder(int n, int[][] connections) { // 邻接表Listint[]每个数组 {neighbor, cost} // cost1原道路是 当前节点→邻居需要翻转 // cost0虚拟反向边不需要翻转 ListListint[] graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } // 构建双向带权图 for (int[] edge : connections) { int u edge[0]; int v edge[1]; graph.get(u).add(new int[]{v, 1}); // u-v 真实路代价1 graph.get(v).add(new int[]{u, 0}); // v-u 虚拟路代价0 } boolean[] visited new boolean[n]; dfs(graph, 0, visited); return res; } private void dfs(ListListint[] graph, int cur, boolean[] visited) { visited[cur] true; // 只遍历当前节点的所有邻接点O(邻接点数量)不是O(n) for (int[] neighborInfo : graph.get(cur)) { int next neighborInfo[0]; int cost neighborInfo[1]; if (!visited[next]) { res cost; dfs(graph, next, visited); } } } }关键优化点对比旧代码缺陷dfs 循环0~n-1所有节点n5e4 直接超时contains()线性查找双重循环叠加复杂度爆炸无法快速区分 “原正向路 / 虚拟反向路”逻辑绕且慢新版优化点邻接表存储带权边一次遍历当前节点所有邻居时间复杂度 O (n)总节点 边只遍历一次去掉List.contains()完全消除线性查找开销建图时直接标记是否需要翻转遍历邻居时直接累加代价逻辑极简整体时间复杂度 O (n)空间 O (n)大数据量无压力补充BFS 迭代版防止递归深度过大栈溢出当 n 极大时递归 DFS 会栈溢出可用 BFSimport java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; class Solution { public int minReorder(int n, int[][] connections) { ListListint[] graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); for (int[] e : connections) { int u e[0], v e[1]; graph.get(u).add(new int[]{v, 1}); graph.get(v).add(new int[]{u, 0}); } boolean[] vis new boolean[n]; QueueInteger q new LinkedList(); q.offer(0); vis[0] true; int ans 0; while (!q.isEmpty()) { int cur q.poll(); for (int[] info : graph.get(cur)) { int next info[0], cost info[1]; if (!vis[next]) { vis[next] true; ans cost; q.offer(next); } } } return ans; } }原理简单说明题目要求所有城市能通向 0从 0 向外遍历如果遍历方向和原始道路方向一致u→v说明这条路远离 0必须翻转计数 1如果是反向虚拟边v→u道路本身朝向 0无需翻转不计入结果 遍历所有节点累加翻转次数即为答案。
dfs代码问题根源分析
目录1. 核心超时原因2. 正确建图思路优化后完整代码DFS 版AC 不超时关键优化点对比旧代码缺陷新版优化点补充BFS 迭代版防止递归深度过大栈溢出原理简单说明1. 核心超时原因双重循环 O (n²)dfs 里写了for(int i 0; i n; i)每次遍历全部 n 个节点n 大时直接爆炸。List.contains () 是 O (k) 线性查找graph.get(pos).contains(i)每次遍历邻接表双重嵌套复杂度极高。图只存单向边没有标记原道路方向原数组connections[a,b]代表原生道路 a→b需要反转而 b→a 是虚拟反向边不用反转。你现在单纯存单向列表判断是否要翻转的逻辑低效且容易出错。2. 正确建图思路每条道路[u, v]u → v真实道路走到这里需要翻转标记权重1v → u虚拟反向通路不用翻转标记权重0邻接表存(邻接点, 是否需要翻转)一次遍历就能拿到所有邻居不用循环全部节点。优化后完整代码DFS 版AC 不超时import java.util.ArrayList; import java.util.List; class Solution { int res 0; public int minReorder(int n, int[][] connections) { // 邻接表Listint[]每个数组 {neighbor, cost} // cost1原道路是 当前节点→邻居需要翻转 // cost0虚拟反向边不需要翻转 ListListint[] graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } // 构建双向带权图 for (int[] edge : connections) { int u edge[0]; int v edge[1]; graph.get(u).add(new int[]{v, 1}); // u-v 真实路代价1 graph.get(v).add(new int[]{u, 0}); // v-u 虚拟路代价0 } boolean[] visited new boolean[n]; dfs(graph, 0, visited); return res; } private void dfs(ListListint[] graph, int cur, boolean[] visited) { visited[cur] true; // 只遍历当前节点的所有邻接点O(邻接点数量)不是O(n) for (int[] neighborInfo : graph.get(cur)) { int next neighborInfo[0]; int cost neighborInfo[1]; if (!visited[next]) { res cost; dfs(graph, next, visited); } } } }关键优化点对比旧代码缺陷dfs 循环0~n-1所有节点n5e4 直接超时contains()线性查找双重循环叠加复杂度爆炸无法快速区分 “原正向路 / 虚拟反向路”逻辑绕且慢新版优化点邻接表存储带权边一次遍历当前节点所有邻居时间复杂度 O (n)总节点 边只遍历一次去掉List.contains()完全消除线性查找开销建图时直接标记是否需要翻转遍历邻居时直接累加代价逻辑极简整体时间复杂度 O (n)空间 O (n)大数据量无压力补充BFS 迭代版防止递归深度过大栈溢出当 n 极大时递归 DFS 会栈溢出可用 BFSimport java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; class Solution { public int minReorder(int n, int[][] connections) { ListListint[] graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); for (int[] e : connections) { int u e[0], v e[1]; graph.get(u).add(new int[]{v, 1}); graph.get(v).add(new int[]{u, 0}); } boolean[] vis new boolean[n]; QueueInteger q new LinkedList(); q.offer(0); vis[0] true; int ans 0; while (!q.isEmpty()) { int cur q.poll(); for (int[] info : graph.get(cur)) { int next info[0], cost info[1]; if (!vis[next]) { vis[next] true; ans cost; q.offer(next); } } } return ans; } }原理简单说明题目要求所有城市能通向 0从 0 向外遍历如果遍历方向和原始道路方向一致u→v说明这条路远离 0必须翻转计数 1如果是反向虚拟边v→u道路本身朝向 0无需翻转不计入结果 遍历所有节点累加翻转次数即为答案。
