fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define all(c) (c).begin(), (c).end()
  6. #define sz(x) (int)(x).size()
  7.  
  8. // MLE
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(0);
  12.     int t;
  13.     cin >> t;
  14.     while (t--) {
  15.         int n, m;
  16.         cin >> n >> m;
  17.         vector<set<int>> adj(n);
  18.         for (int i = 0; i < n - 1; i++) {
  19.             for (int j = i + 1; j < n; j++) {
  20.                 adj[i].insert(j);
  21.             }
  22.         }
  23.         for (int i = 0; i < m; i++) {
  24.             int a, b;
  25.             cin >> a >> b;
  26.             --a, --b;
  27.             adj[a].erase(b);
  28.         }
  29.  
  30.         // Topology sort
  31.         vector<int> in_degree(n, 0);
  32.         for (int i = 0; i < n; i++) {
  33.             for (int child : adj[i]) {
  34.                 in_degree[child]++;
  35.             }
  36.         }
  37.         priority_queue<int> q;
  38.         for (int i = 0; i < n; i++) {
  39.             if (in_degree[i] == 0) q.push(i);
  40.         }
  41.         int cnt = 0;
  42.         vector<int> ans;
  43.         while (!q.empty()) {
  44.             int x = q.top();
  45.             q.pop();
  46.             ans.push_back(x + 1);
  47.             for (int child : adj[x]) {
  48.                 if (--in_degree[child] == 0) q.push(child);
  49.             }
  50.             cnt++;
  51.         }
  52.         if (cnt != n) assert(false);
  53.         for (int i = 0; i < sz(ans); i++) {
  54.             cout << ans[i] << " \n"[i == sz(ans) - 1];
  55.         }
  56.     }
  57.     return 0;
  58. }
  59.  
  60.  
Runtime error #stdin #stdout 4.56s 2895500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wdJl12
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!