与えられた依存関係からすべてのタスクを完了することが可能かどうかをチェックするC++プログラム

この記事では、指定された前提条件に基づいて、指定されたすべてのタスクを完了できるかどうかを確認するプログラムについて説明します。

たとえば、3つのタスクが与えられ、前提条件が[[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;
// 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