从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