fork download
  1. //bài toán:Có n công việc (đánh số từ 1 → n)
  2. //Có m yêu cầu dạng (u, v) nghĩa là phải làm u trước v.
  3. //In ra thứ tự làm các công việc thoả mãn m yêu cầu. Nếu không có cách, in IMPOSSIBLE
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. int main() {
  8. ios::sync_with_stdio(false);
  9. cin.tie(nullptr);
  10.  
  11. int n, m;
  12. cin >> n >> m;
  13.  
  14. vector<vector<int>> adj(n + 1);
  15. vector<int> indegree(n + 1, 0);
  16.  
  17. // Đọc các yêu cầu
  18. for (int i = 0; i < m; i++) {
  19. int u, v;
  20. cin >> u >> v;
  21. adj[u].push_back(v);
  22. indegree[v]++;
  23. }
  24.  
  25. queue<int> q;
  26.  
  27. // Đưa các công việc không có yêu cầu trước vào queue
  28. for (int i = 1; i <= n; i++) {
  29. if (indegree[i] == 0) {
  30. q.push(i);
  31. }
  32. }
  33.  
  34. vector<int> topo_order;
  35.  
  36. while (!q.empty()) {
  37. int u = q.front();
  38. q.pop();
  39. topo_order.push_back(u);
  40.  
  41. for (int v : adj[u]) {
  42. indegree[v]--;
  43. if (indegree[v] == 0) {
  44. q.push(v);
  45. }
  46. }
  47. }
  48.  
  49. // Nếu chưa lấy đủ n đỉnh nghĩa là có chu trình, có 1 tập các công việc bị phụ thuộc vào nhau
  50. if ((int)topo_order.size() != n) {
  51. cout << "IMPOSSIBLE\n";
  52. } else {
  53. for (int x : topo_order) {
  54. cout << x << " ";
  55. }
  56. cout << "\n";
  57. }
  58.  
  59. return 0;
  60. }
Success #stdin #stdout 0s 5320KB
stdin
4 3
1 2
1 3
3 2
stdout
1 4 3 2