C++で指定された依存関係からタスクの順序を見つけます

n個の異なるタスクがあるとします。これらのタスクには、0からn-1までのラベルが付けられています。一部のタスクには前提条件のタスクがある場合があるため、例として、タスク2を選択する場合は、最初にタスク1を終了する必要があります。これはペアとして表されます-[2、1]タスクの総数とリストがある場合前提条件のペアのうち、すべてのタスクを完了するには、タスクの順序を見つける必要があります。正しい注文が複数ある場合は、そのうちの1つを返品できます。また、指定されたすべてのタスクを完了することが不可能な場合は、空の配列を返します。

したがって、入力がn =4で、A =[[1、0]、[2、0]、[3、2]、[3、1]、[4,2]]の場合、出力は次のようになります。 [0、2、1、4、3]

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これにより、グラフ、開始、オンパス、訪問された配列、配列toposort、

  が取得されます。

• 訪問済み[開始]がマークされている場合、-

  • falseを返す

• onpath [start]：=true、visited [start]：=true

• グラフ[開始]の各ネイバーについて、実行

  • onpath [neighbor]がtrueの場合、またはdfs（graph、neighbor、onpath、visited、toposort）がtrueの場合、-

    • trueを返す

  • toposortの最後にstartを挿入

• onpath [start]：=false

  を返します

• メインの方法から、次のようにします-

• グラフ=事前配列に格納されたn個の頂点とエッジを使用してグラフを作成します

• 配列トポソートを定義する

• サイズnの配列onpathを定義し、falseで埋めます

• サイズnの訪問済み配列を定義し、falseで埋めます

• 初期化i：=0の場合、i

  • visited [i]がfalseで、dfs（graph、i、onpath、visited、toposort）がtrueの場合、-

    • 空白の配列を返す

• 配列toposortを逆にします

• toposortに戻る

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
   vector<unordered_set<int> > graph(n);
   for (auto pre : pre)
      graph[pre.second].insert(pre.first);
   return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
   if (visited[start])
      return false;
   onpath[start] = visited[start] = true;
   for (int neigh : graph[start])
      if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
         return true;
   toposort.push_back(start);
   return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
   vector<unordered_set<int> > graph = create_graph(n, pre);
   vector<int> toposort;
   vector<bool> onpath(n, false), visited(n, false);
   for (int i = 0; i < n; i++)
      if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
         return {};
   reverse(toposort.begin(), toposort.end());
   return toposort;
}
int main() {
   int n = 4;
   vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
   vector<int> v = get_order(n, pre);
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
   }
}

入力

4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}

出力

0 1 4 2 3