資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式檢查是否可以完成所有給定依賴項的任務
在本文中，我們將討論一個程式，該程式根據給定的先決條件檢查是否可以完成所有給定的任務。
例如，假設我們得到了三個任務，並且先決條件為 [[1, 0], [2, 1], [3, 2]]。
（[1,0] 表示要選擇“1”任務；必須先完成“0”任務。）
那麼，在這個例子中，由於“0”任務沒有任何先決條件，因此可以首先完成。然後可以完成“1”任務，因為“0”任務已完成。同樣，“2”和“3”任務也可以完成。因此，在這種情況下，答案將是“True”。
這個問題可以使用圖演算法解決。由於陣列在圖演算法中不方便，我們將將其轉換為圖。這可以透過從任務“m”到任務“n”建立一條邊來完成，如果任務“n”依賴於完成“m”。
建立圖後，我們可以使用DFS。其中，我們可以從特定節點開始，然後訪問其最近的節點，然後訪問該節點的最近節點，依此類推。如果我們遇到先前已訪問過的節點，則會形成一個迴圈，我們將返回“False”。否則，一旦到達終端，此模式將再次由另一個節點遵循，直到訪問圖中的所有節點。如果已訪問所有節點，我們將返回“True”。
示例
#include <bits/stdc++.h>
using namespace std;
// Converts list into graph
vector<unordered_set<int> > make_graph(int Tasks, vector<pair<int, int> >& dependencies) {
vector<unordered_set<int> > graph(Tasks);
for (auto pre : dependencies)
graph[pre.second].insert(pre.first);
return graph;
}
//to check if all the nodes are visited
bool cycle(vector<unordered_set<int> >& graph, int node, vector<bool>& onway, vector<bool>& visited) {
if (visited[node])
return false;
onway[node] = visited[node] = true;
for (int near : graph[node]) {
if (onway[near] || cycle(graph, near, onway, visited))
return true;
}
return onway[node] = false;
}
//to check if all the tasks can be completed
bool canFinish(int Tasks, vector<pair<int, int> >& dependencies) {
vector<unordered_set<int>>graph = make_graph(Tasks, dependencies);
vector<bool> onway(Tasks, false), visited(Tasks, false);
for (int i = 0; i < Tasks; i++) {
if (!visited[i] && cycle(graph, i, onway, visited))
return false;
}
return true;
}
int main() {
int Tasks = 6;
vector<pair<int, int >> dependencies;
dependencies.push_back(make_pair(1, 0));
dependencies.push_back(make_pair(2, 1));
dependencies.push_back(make_pair(3, 2));
dependencies.push_back(make_pair(5, 3));
dependencies.push_back(make_pair(4, 5));
if (canFinish(Tasks, dependencies)) {
cout << "True";
}
else {
cout << "False";
}
return 0;
}輸出
True
更新於: 2019年10月3日
121 次瀏覽
廣告