資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學在 C++ 中查詢給定依賴項的任務排序
假設我們有 n 個不同的任務；這些任務從 0 到 n-1 標記。某些任務可能具有先決條件任務，例如，如果我們想要選擇任務 2，那麼我們必須首先完成任務 1，這表示為一對 - [2, 1] 如果我們有任務總數和先決條件對列表，我們必須找到完成所有任務的任務排序。如果有多個正確的順序，我們可以只返回其中一個。如果無法完成所有給定的任務，則返回一個空陣列。
因此，如果輸入類似於 n = 4，並且 A = [[1, 0], [2, 0], [3, 2], [3, 1],[4,2]]，則輸出將為 [0, 2, 1, 4, 3]
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 dfs()，它將接收圖、起點、onpath、一個已訪問陣列、一個拓撲排序陣列作為引數。
如果 visited[start] 被標記，則 -
返回 false
onpath[start] := true，visited[start] := true
對於 graph[start] 中的每個鄰居，執行以下操作
如果 onpath[neighbor] 為 true 或 dfs(graph, neighbor, onpath, visited, toposort) 為 true，則 -
返回 true
在 toposort 的末尾插入 start
返回 onpath[start] := false
從主方法中執行以下操作 -
graph = 建立一個具有 n 個頂點和儲存在 pre 陣列中的邊的圖
定義一個數組 toposort
定義一個大小為 n 的陣列 onpath 並填充 false
定義一個大小為 n 的陣列 visited 並填充 false
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行以下操作 -
如果 visited[i] 為 false 且 dfs(graph, i, onpath, visited, toposort) 為 true，則 -
返回空陣列
反轉陣列 toposort
返回 toposort
示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
vector<unordered_set<int> > graph(n);
for (auto pre : pre)
graph[pre.second].insert(pre.first);
return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
if (visited[start])
return false;
onpath[start] = visited[start] = true;
for (int neigh : graph[start])
if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
return true;
toposort.push_back(start);
return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
vector<unordered_set<int> > graph = create_graph(n, pre);
vector<int> toposort;
vector<bool> onpath(n, false), visited(n, false);
for (int i = 0; i < n; i++)
if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
return {};
reverse(toposort.begin(), toposort.end());
return toposort;
}
int main() {
int n = 4;
vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
vector<int> v = get_order(n, pre);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
}輸入
4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}輸出
0 1 4 2 3
382 次檢視
