服务类网站怎么做,中国的搜索引擎有哪些,.net搭建企业网站,wordpress数据文件路径#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ DFS 图 树 求解思路 实现代码 运行结果 共勉 题目链接
1466. 重新规划路线
⛲ 题目描述
n 座城市从 0 到 n-1 编号其间共有 n-1 条路线。因此要想在两座不同城市之间旅行只有唯一一条路线可供选择路线网形成一颗树。去年交通运输部决定重新规划路线以改变交通拥堵的状况。
路线用 connections 表示其中 connections[i] [a, b] 表示从城市 a 到 b 的一条有向路线。
今年城市 0 将会举办一场大型比赛很多游客都想前往城市 0 。
请你帮助重新规划路线方向使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。
示例 1 输入n 6, connections [[0,1],[1,3],[2,3],[4,0],[4,5]] 输出3 解释更改以红色显示的路线的方向使每个城市都可以到达城市 0 。 示例 2 输入n 5, connections [[1,0],[1,2],[3,2],[3,4]] 输出2 解释更改以红色显示的路线的方向使每个城市都可以到达城市 0 。 示例 3
输入n 3, connections [[1,0],[2,0]] 输出0
提示
2 n 5 * 10^4 connections.length n-1 connections[i].length 2 0 connections[i][0], connections[i][1] n-1 connections[i][0] ! connections[i][1] 求解思路实现代码运行结果 ⚡ DFS 图 树 求解思路
给定的n个点n−1条边构成的有向图题目的要求是重新规划路线更改不能到达0的方向路线最后求所有点到0点最小改变次数。可以忽略边的方向有向图直接变成了一棵树。需要改变某些边的方向使得每个点都可以访问到 0点那么我们从0节点开始通过dfs(son,father)来求解整个过程。同时在进行dfs之前我们需要标记代价connections原始方向使用1标记原方向的边使用0标记反向边。实现代码如下所示 实现代码
class Solution {private ArrayListint[][] list;public int minReorder(int n, int[][] connections) {this.listnew ArrayList[n];Arrays.setAll(list,e-new ArrayList());for(int[] conn:connections){list[conn[0]].add(new int[]{conn[1],1});list[conn[1]].add(new int[]{conn[0],0});}return dfs(0,-1);}public int dfs(int x,int father){int ans0;for(int[] next:list[x]){if(father!next[0]){ansnext[1]dfs(next[0],x);}}return ans;}}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
