資料結構
網路
關係資料庫管理系統 (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 次瀏覽
