Advertisement
mickypinata

KOI: Sandro

Dec 6th, 2021
576
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e4 + 5;
  5.  
  6. vector<int> adj[N];
  7. int inDeg[N];
  8.  
  9. int main(){
  10.  
  11.     int nVertex, nEdge;
  12.     scanf("%d%d", &nVertex, &nEdge);
  13.     for(int i = 1; i <= nEdge; ++i){
  14.         int u, v;
  15.         scanf("%d%d", &u, &v);
  16.         adj[u].push_back(v);
  17.         ++inDeg[v];
  18.     }
  19.     priority_queue<int, vector<int>, greater<int>> pq;
  20.     for(int i = 1; i <= nVertex; ++i){
  21.         if(inDeg[i] == 0){
  22.             pq.push(i);
  23.         }
  24.     }
  25.     vector<int> topo;
  26.     while(!pq.empty()){
  27.         int u = pq.top();
  28.         pq.pop();
  29.         topo.push_back(u);
  30.         for(int v : adj[u]){
  31.             --inDeg[v];
  32.             if(inDeg[v] == 0){
  33.                 pq.push(v);
  34.             }
  35.         }
  36.     }
  37.     if(topo.size() < nVertex){
  38.         cout << "-1";
  39.     } else {
  40.         for(int x : topo){
  41.             cout << x << ' ';
  42.         }
  43.     }
  44.  
  45.     return 0;
  46. }
  47.  
Advertisement
RAW Paste Data Copied
Advertisement