制作一个视频网站,网站网页优化怎么做,扶风网站开发,行业门户网站是什么1466. 重新规划路线
n 座城市#xff0c;从 0 到 n-1 编号#xff0c;其间共有 n-1 条路线。因此#xff0c;要想在两座不同城市之间旅行只有唯一一条路线可供选择#xff08;路线网形成一颗树#xff09;。去年#xff0c;交通运输部决定重新规划路线#xff0c;以改变…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]
有两种解法BFS或者DFS:
DFS解法
参考力扣官方解法 思路与算法
题目给定一张由 nnn 个点使用 000 到 n−1n-1n−1 编号n−1n-1n−1 条边构成的有向图如果忽略边的方向就变成了一棵树。我们需要改变某些边的方向使得每个点都可以访问到 000 号点。
如果忽略边的方向将每条有向边以及其反向边加入到图中那么从任意一点出发都能到达 000 号点。路径上可能会经过反向边我们需要变更与之对应的原边的方向。需要变更的次数即为答案。
以每个点为起点进行搜索的代价会很大因此我们考虑从 000 出发去遍历其他点可以使用深度优先搜索或者广度优先搜索本题解使用深度优先搜索原来我们需要统计反向边的数量现在需要统计原方向边的数量。
具体而言我们使用 111 标记原方向的边使用 000 标记反向边。然后从 000 号点开始遍历访问到某个新的点时所经过的边被 111 标记就令答案加 111。最终统计得到的答案就是我们需要变更方向的最小路线数。
class Solution {
public:int dfs(int x, int parent, vectorvectorpairint, int e) {int res 0;for (auto edge : e[x]) {if (edge.first parent) {continue;}res edge.second dfs(edge.first, x, e);}return res;}int minReorder(int n, vectorvectorint connections) {vectorvectorpairint, int e(n);for (auto edge : connections) {e[edge[0]].push_back(make_pair(edge[1], 1));e[edge[1]].push_back(make_pair(edge[0], 0));}return dfs(0, -1, e);}
};以下是我的解法 BFS
当我们面对这个问题时我们的目标是重新规划路线方向使得每个城市都能到达城市 0。给定的城市和路线信息可以表示成一个有向图其中每个节点是城市每条边是一条有向的路线。为了达到目标我们需要确保从每个城市到城市 0 都有一条有向路径。 所以方法很明显了 首先建立有向图然后bfs遍历再计算反向边数即可
class Solution {
public:int minReorder(int n, std::vectorstd::vectorint connections) {std::vectorstd::vectorstd::pairint, int graph(n); // 使用邻接表表示有向图// 构建有向图for (const auto edge : connections) {graph[edge[0]].emplace_back(edge[1], 1); // 原方向graph[edge[1]].emplace_back(edge[0], 0); // 反方向}std::vectorbool visited(n, false);int minReorderCount 0;// 从城市0开始执行BFS遍历std::queueint q;q.push(0);visited[0] true;while (!q.empty()) {int currentCity q.front();q.pop();for (const auto neighbor : graph[currentCity]) {int nextCity neighbor.first;int direction neighbor.second;if (!visited[nextCity]) {// 如果需要反转边的方向增加计数minReorderCount direction;// 移动到BFS遍历中的下一个城市q.push(nextCity);visited[nextCity] true;}}}return minReorderCount;}
};
