数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中重新排序路线以使所有路径通向城市零
假设有n个不同的城市，编号从0到n-1，并且有n-1条道路，使得两个不同城市之间只有一条路径。假设交通部决定将道路单向通行，因为道路太窄了。
这里道路由连接表示，其中connections[i] = [a, b]表示从城市a到城市b的一条道路。
如果首都（编号为0的城市）发生重大事件，许多人想前往该城市。我们必须对某些道路进行重新定向，以便每个城市都能到达城市0。我们必须找到需要更改的最小边数。
因此，如果输入是6，connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]，
则输出为3，因为我们必须更改红色所示边的方向，以便每个节点都能到达首都。
为了解决这个问题，我们将遵循以下步骤：
定义两个大小为N = 5*10^4 + 5的列表数组graph1、graph2。
从主方法执行以下操作：
定义一个map in
对于每个元素it in e，执行：
将it[1]插入到graph1[it[0]]的末尾
将it[0]插入到graph2[it[1]]的末尾
定义一个大小为n的数组dist，并将其填充为N + 10
ret := 0, in[0] := 0, dist[0] := 0
定义一个队列q
将0插入到q中
定义一个集合visited
将0插入到visited中
当(q不为空)时，执行：
node := q的第一个元素
从q中删除元素
ret := ret + dist[node]
对于每个元素it in graph2[node]，执行：
如果it未被访问且dist[it] > 0，则：
dist[it] := 0
将it插入到q中
将it插入到visited中
对于每个元素it in graph1[node]，执行：
如果it未被访问且dist[it] > 1，则：
dist[it] := 1
将it插入到q中
将it插入到visited中
返回ret
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
class Solution {
public:
vector<int> graph1[N];
vector<int> graph2[N];
int minReorder(int n, vector<vector<int> >& e){
map<int, int> in;
for (auto& it : e) {
graph1[it[0]].push_back(it[1]);
graph2[it[1]].push_back(it[0]);
}
vector<int> dist(n, N + 10);
int ret = 0;
in[0] = 0;
dist[0] = 0;
queue<int> q;
q.push(0);
set<int> visited;
visited.insert(0);
while (!q.empty()) {
int node = q.front();
q.pop();
ret += dist[node];
for (auto& it : graph2[node]) {
if (!visited.count(it) && dist[it] > 0) {
dist[it] = 0;
q.push(it);
visited.insert(it);
}
}
for (auto& it : graph1[node]) {
if (!visited.count(it) && dist[it] > 1) {
dist[it] = 1;
q.push(it);
visited.insert(it);
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1},{1,3},{2,3},{4,0},{4,5}};
cout << (ob.minReorder(6,v));
}输入
6,{{0,1},{1,3},{2,3},{4,0},{4,5}}输出
3
397 次浏览
