fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int t;
  9.     cin >> t;
  10.  
  11.     while (t--) {
  12.         int n, m;
  13.         cin >> n >> m;
  14.  
  15.         // Topological sort using Kahn's algorithm
  16.         // Goal: find lexicographically smallest valid ordering of tasks
  17.  
  18.         // adj[i] stores all tasks that come after task i
  19.         vector<vector<int>> adj(n + 1);
  20.  
  21.         // deg[i] = incoming edges (how many tasks must be done before task i)
  22.         vector<int> deg(n + 1, 0);
  23.  
  24.         // Build the directed graph
  25.         for (int i = 0; i < m; i++) {
  26.             int a, b;
  27.             cin >> a >> b;  // a must come before b
  28.             adj[a].push_back(b);
  29.             deg[b]++;
  30.         }
  31.  
  32.         // Min heap - always pick smallest numbered task available
  33.         // This ensures lexicographically smallest ordering
  34.         priority_queue<int, vector<int>, greater<int>> pq;
  35.  
  36.         // Start with tasks that have no dependencies (in-degree = 0)
  37.         for (int i = 1; i <= n; i++) {
  38.             if (deg[i] == 0) {
  39.                 pq.push(i);
  40.             }
  41.         }
  42.  
  43.         vector<int> ans;
  44.  
  45.         // Process tasks in topological order
  46.         while (!pq.empty()) {
  47.             int curr = pq.top();
  48.             pq.pop();
  49.             ans.push_back(curr);
  50.  
  51.             // Remove this task from graph
  52.             // Check if any dependent tasks are now ready
  53.             for (int next : adj[curr]) {
  54.                 deg[next]--;
  55.                 if (deg[next] == 0) {
  56.                     pq.push(next);
  57.                 }
  58.             }
  59.         }
  60.  
  61.         // If we couldn't process all tasks, there's a cycle
  62.         if (ans.size() != n) {
  63.             cout << -1 << "\n";
  64.         } else {
  65.             for (int i = 0; i < n; i++) {
  66.                 if (i > 0) cout << " ";
  67.                 cout << ans[i];
  68.             }
  69.             cout << "\n";
  70.         }
  71.     }
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
4 3
1 2
1 3
3 4
3 3
1 2
2 3
3 1
5 0
stdout
copy 
1 2 3 4
-1
1 2 3 4 5
https://ideone.com/6roMHT
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!