从C ++中的给定依赖关系中找到任务的顺序

假设我们有n个不同的任务；这些任务被标记为从0到n-1。某些任务可能具有先决条件任务，因此，例如，如果我们要选择任务2，则必须首先完成任务1，将其表示为一对-[2，1]如果我们有任务总数和列表在先决条件对中，我们必须找到任务的顺序才能完成所有任务。如果有多个正确的订单，我们可以退回其中之一。如果不可能完成所有给定的任务，则返回一个空数组。

因此，如果输入为n = 4，并且A = [[[1，0]，[2，0]，[3，2]，[3，1]，[4,2]]，则输出将为是[0，2，1，4，3]

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数dfs()，它将使用图，开始，一个onpath，一个访问过的数组，一个数组拓扑，

• 如果标记了visit [start]，则-

• 返回假

• onpath [start]：= true，访问过[start]：= true

• 对于图中的每个邻居[开始]，执行

• 返回真

• 如果onpath [neighbor]为true或dfs（图形，邻居，onpath，已访问，拓扑排序）为true，则-

• 在拓扑末尾插入开始

• 返回onpath [start]：= false

• 从主要方法中，执行以下操作-

• graph =使用预先存储的n个顶点和边创建图

• 定义数组拓扑

• 定义大小为n的数组onpath并用false填充

• 定义一个大小为n的访问数组，并用false填充

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 返回空白数组

• 如果visited [i]为假并且dfs(graph,i,onpath,Visited,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