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：真实道路，走到这里需要翻转，标记权重
1 - v → u：虚拟反向通路，不用翻转，标记权重
0邻接表存(邻接点, 是否需要翻转)，一次遍历就能拿到所有邻居，不用循环全部节点。
优化后完整代码（DFS 版，AC 不超时）
import java.util.ArrayList; import java.util.List; class Solution { int res = 0; public int minReorder(int n, int[][] connections) { // 邻接表：List<int[]>，每个数组 {neighbor, cost} // cost=1：原道路是 当前节点→邻居，需要翻转 // cost=0：虚拟反向边，不需要翻转 List<List<int[]>> 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(List<List<int[]>> 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所有节点，n=5e4 直接超时 contains()线性查找，双重循环叠加复杂度爆炸- 无法快速区分 “原正向路 / 虚拟反向路”，逻辑绕且慢
新版优化点
- 邻接表存储带权边一次遍历当前节点所有邻居，时间复杂度 O (n)，总节点 + 边只遍历一次
- 去掉
List.contains()，完全消除线性查找开销 - 建图时直接标记是否需要翻转，遍历邻居时直接累加代价，逻辑极简
- 整体时间复杂度 O (n)，空间 O (n)，大数据量无压力
补充：BFS 迭代版（防止递归深度过大栈溢出）
当 n 极大时，递归 DFS 会栈溢出，可用 BFS：
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; class Solution { public int minReorder(int n, int[][] connections) { List<List<int[]>> 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]; Queue<Integer> 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，无需翻转，不计入结果 遍历所有节点累加翻转次数即为答案。