C ++程序检查是否可以根据给定的依赖项完成所有任务

Z时代
2024-01-10
分类：综合

在本文中，我们将讨论一个程序，以检查是否有可能根据给定的先决条件完成所有给定的任务。

例如，让我们说我们得到了三个任务，先决条件是[[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;
}