C ++程序检查是否可以根据给定的依赖项完成所有任务
在本文中，我们将讨论一个程序，以检查是否有可能根据给定的先决条件完成所有给定的任务。
例如，让我们说我们得到了三个任务，先决条件是[[1，0]，[2，1]，[3，2]]。
（[1,0]表示要接听“1”任务；必须先完成“0”任务。）
然后，在此示例中，由于“0”任务没有任何先决条件，因此可以首先完成。然后，由于已完成“0”任务，因此可以完成“1”任务。同样，“2”和“3”任务也可以完成。因此，在这种情况下，答案将是“正确”。
可以使用图形算法解决此问题。由于数组在图算法中不方便，因此我们将其转换为图。如果任务“n”具有依赖关系作为“m”的完成，则可以通过从任务“m”到任务“n”之间形成优势来完成。
绘制图形后，我们可以使用DFS。这样，我们可以从特定节点开始，然后访问其最近的节点，然后访问该节点最近的节点，依此类推。如果遇到先前已访问过的节点，则会进行循环并返回“False”。否则，一旦我们到达终端，此模式将再次跟随另一个节点，直到访问了图中的所有节点。如果已经到达所有节点，我们将返回“True”。
示例
#include <bits/stdc++.h>
using namespace std;
//将列表转换为图形
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;
}
//检查是否所有节点都已访问
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;
}
//检查所有任务是否可以完成
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