Trong bài viết này, chúng ta sẽ thảo luận về một chương trình để kiểm tra xem liệu có thể hoàn thành tất cả các nhiệm vụ đã cho trên cơ sở các điều kiện tiên quyết đã cho hay không.
Ví dụ:giả sử chúng tôi đã được giao ba nhiệm vụ và điều kiện tiên quyết là [[1, 0], [2, 1], [3, 2]].
([1,0] có nghĩa là để nhận nhiệm vụ ‘1’; nhiệm vụ ‘0’ phải được hoàn thành trước tiên.)
Sau đó, trong ví dụ này vì nhiệm vụ "0" không có bất kỳ điều kiện tiên quyết nào nên có thể hoàn thành trước. Sau đó, nhiệm vụ ‘1’ có thể được hoàn thành, vì nhiệm vụ ‘0’ đã được hoàn thành. Tương tự, cả hai nhiệm vụ ‘2’ và ‘3’ cũng có thể được hoàn thành. Vì vậy, câu trả lời trong trường hợp này sẽ là "Đúng".
Vấn đề này có thể được giải quyết bằng cách sử dụng các thuật toán đồ thị. Vì các mảng không thuận tiện với các thuật toán đồ thị, chúng tôi sẽ chuyển đổi nó thành một biểu đồ. Điều này có thể được thực hiện bằng cách tạo một cạnh từ nói nhiệm vụ ‘m’ thành nhiệm vụ ‘n’, nếu nhiệm vụ ‘n’ có sự phụ thuộc khi hoàn thành ‘m’.
Khi đồ thị được tạo, chúng ta có thể sử dụng DFS. Trong đó, chúng ta có thể bắt đầu từ một nút cụ thể và sau đó truy cập vào nút gần nhất của nó và sau đó là nút gần nhất với nút đó, v.v. Nếu chúng ta gặp một nút đã được truy cập trước đó, một chu kỳ sẽ được thực hiện và chúng ta sẽ trả về "Sai". Nếu không, khi chúng ta đến một thiết bị đầu cuối, mô hình này sẽ lại được theo sau bởi một nút khác cho đến khi tất cả các nút trong biểu đồ đã được truy cập. Nếu tất cả các nút đã đạt được, chúng tôi sẽ trả về "True".
Ví dụ
#include <bits/stdc++.h>
using namespace std;
// Converts list into graph
vector<unordered_set<int> > make_graph(int Tasks, vector<pair<int, int> >& dependencies) {
vector<unordered_set<int> > graph(Tasks);
for (auto pre : dependencies)
graph[pre.second].insert(pre.first);
return graph;
}
//to check if all the nodes are visited
bool cycle(vector<unordered_set<int> >& graph, int node, vector<bool>& onway, vector<bool>& visited) {
if (visited[node])
return false;
onway[node] = visited[node] = true;
for (int near : graph[node]) {
if (onway[near] || cycle(graph, near, onway, visited))
return true;
}
return onway[node] = false;
}
//to check if all the tasks can be completed
bool canFinish(int Tasks, vector<pair<int, int> >& dependencies) {
vector<unordered_set<int>>graph = make_graph(Tasks, dependencies);
vector<bool> onway(Tasks, false), visited(Tasks, false);
for (int i = 0; i < Tasks; i++) {
if (!visited[i] && cycle(graph, i, onway, visited))
return false;
}
return true;
}
int main() {
int Tasks = 6;
vector<pair<int, int >> dependencies;
dependencies.push_back(make_pair(1, 0));
dependencies.push_back(make_pair(2, 1));
dependencies.push_back(make_pair(3, 2));
dependencies.push_back(make_pair(5, 3));
dependencies.push_back(make_pair(4, 5));
if (canFinish(Tasks, dependencies)) {
cout << "True";
}
else {
cout << "False";
}
return 0;
} Đầu ra
True