数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告