最新网站建设进程,门户网站开发 论文,汕头市通信建设管理办公室网站,微盟做一个小程序大概多少钱题目描述 n 座城市#xff0c;从 0 到 n-1 编号#xff0c;其间共有 n-1 条路线。因此#xff0c;要想在两座不同城市之间旅行只有唯一一条路线可供选择#xff08;路线网形成一颗树#xff09;。去年#xff0c;交通运输部决定重新规划路线#xff0c;以改变交通拥堵的…题目描述 n 座城市从 0 到 n-1 编号其间共有 n-1 条路线。因此要想在两座不同城市之间旅行只有唯一一条路线可供选择路线网形成一颗树。去年交通运输部决定重新规划路线以改变交通拥堵的状况。路线用 connections 表示其中 connections[i] [a, b] 表示从城市 a 到 b 的一条有向路线。今年城市 0 将会举办一场大型比赛很多游客都想前往城市 0 。请你帮助重新规划路线方向使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。
解析 对图从0号城市开始遍历如果不看方向是连通图因此是可以全部遍历的那么如果是顺着遍历的说明是从0往外指的因此方向需要改变否则不变。如果用邻接矩阵会超出内存需要使用邻接表。
public int minReorder(int n, int[][] connections) {Listint[][] e new List[n];for (int i 0; i n; i) {e[i] new ArrayListint[]();}for (int[] edge : connections) {e[edge[0]].add(new int[]{edge[1], 1});e[edge[1]].add(new int[]{edge[0], 0});}return dfs(0, -1, e);}public int dfs(int x, int parent, Listint[][] e) {int res 0;for (int[] edge : e[x]) {if (edge[0] parent) {continue;}res edge[1] dfs(edge[0], x, e);}return res;}
