dfs图遍历 LeetCode1466. 重新规划路线

本文主要是介绍dfs图遍历 LeetCode1466. 重新规划路线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。

路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。

今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。

请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。

因为图是一个连通图，建图时把图看成一个无向图，实际存在的边权值为1，不存在的边权值为0，可以 从 顶点 0 遍历到所有顶点。遇到权值为0的边，

如果遇到反向的边，结果加1。

所以从0开始遍历，加上边的权值即可。

class Solution {
public:vector<vector<pair<int,int>>>g;int res=0;void dfs(int cur,int pre){for(auto ne:g[cur]){if(ne.first==cur||ne.first==pre)continue;res+=ne.second;dfs(ne.first,cur);}}int minReorder(int n, vector<vector<int>>& edge) {g.resize(n);for(int i=0;i<n-1;i++){g[edge[i][0]].push_back({edge[i][1],1});g[edge[i][1]].push_back({edge[i][0],0});}dfs(0,-1);return res;}
};

这篇关于dfs图遍历 LeetCode1466. 重新规划路线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---