Giả sử chúng ta có n nhiệm vụ khác nhau; các nhiệm vụ này được gắn nhãn từ 0 đến n-1. Một số nhiệm vụ có thể có các nhiệm vụ điều kiện tiên quyết, vì vậy, chẳng hạn như nếu chúng ta muốn chọn nhiệm vụ 2 thì trước tiên chúng ta phải hoàn thành nhiệm vụ 1, được biểu thị dưới dạng một cặp - [2, 1] Nếu chúng ta có tổng số nhiệm vụ và danh sách của các cặp điều kiện tiên quyết, chúng ta phải tìm thứ tự các nhiệm vụ để hoàn thành tất cả các nhiệm vụ. Nếu có nhiều hơn một đơn đặt hàng chính xác, chúng tôi chỉ có thể trả lại một trong số chúng. Và nếu không thể hoàn thành tất cả các nhiệm vụ đã cho, hãy trả về một mảng trống.
Vì vậy, nếu đầu vào là n =4 và A =[[1, 0], [2, 0], [3, 2], [3, 1], [4,2]], thì đầu ra sẽ là [0, 2, 1, 4, 3]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm dfs (), hàm này sẽ lấy đồ thị, bắt đầu, một đường dẫn trực tiếp, một mảng được truy cập, một toposort mảng,
-
nếu đã truy cập [bắt đầu] được đánh dấu, thì -
-
trả về false
-
-
onpath [start]:=true, đã truy cập [start]:=true
-
đối với mỗi hàng xóm trong biểu đồ [start], thực hiện
-
nếu onpath [hàng xóm] là đúng hoặc dfs (đồ thị, hàng xóm, trên đường dẫn, đã thăm, toposort) là đúng, thì -
-
trả về true
-
-
chèn bắt đầu vào cuối toposort
-
-
return onpath [start]:=false
-
Từ phương thức chính, thực hiện như sau -
-
graph =tạo đồ thị với n đỉnh và cạnh được lưu trữ trong mảng trước
-
Xác định toposort mảng
-
Xác định một đường dẫn mảng có kích thước n và điền bằng false
-
Xác định một mảng được truy cập có kích thước n và điền sai
-
để khởi tạo i:=0, khi i
-
nếu visit [i] là false và dfs (graph, i, onpath, Visit, toposort) là true, thì -
-
trả về mảng trống
-
-
-
đảo ngược toposort mảng
-
return toposort
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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] << " ";
}
} Đầu vào
4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}} Đầu ra
0 1 4 2 3