数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学在 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、一个已访问数组、一个拓扑排序数组作为参数。
如果 visited[start] 被标记，则 -
返回 false
onpath[start] := true，visited[start] := true
对于 graph[start] 中的每个邻居，执行以下操作
如果 onpath[neighbor] 为 true 或 dfs(graph, neighbor, onpath, visited, toposort) 为 true，则 -
返回 true
在 toposort 的末尾插入 start
返回 onpath[start] := false
从主方法中执行以下操作 -
graph = 创建一个具有 n 个顶点和存储在 pre 数组中的边的图
定义一个数组 toposort
定义一个大小为 n 的数组 onpath 并填充 false
定义一个大小为 n 的数组 visited 并填充 false
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行以下操作 -
如果 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
382 次查看
