Guest User

Untitled

a guest
Oct 18th, 2015
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define endl                '\n'
  6.  
  7. int n,m;
  8.  
  9. vector<int> G2[200002];
  10. int OUTDEG[222222];
  11. bool u[222222];
  12.  
  13. int main( void ) {
  14.     cin.tie( 0 ); cin.sync_with_stdio( 0 );
  15.     set<pair<int,int> > S;
  16.     cin >> n >> m;
  17.     for (int i = 0; i < m; i++) {
  18.         int a,b;
  19.         cin >> a >> b;
  20.         a--,b--;
  21.         if (S.find(make_pair(a,b)) != S.end()) continue;
  22.         S.insert(make_pair(a,b));
  23.         G2[b].push_back(a);
  24.         OUTDEG[a]++;
  25.     }
  26.     vector<int> R;
  27.     int cur = 0;
  28.     while (cur < n) {
  29.         priority_queue<int> Q;
  30.         vector<int> RR;
  31.         Q.push(cur);
  32.         while (Q.size()) {
  33.             int v = Q.top();
  34.             Q.pop();
  35.             RR.push_back(v);
  36.             for (int i = 0; i < (int)G2[v].size(); i++) {
  37.                 int vv = G2[v][i];
  38.                 if (u[vv]) continue;
  39.                 OUTDEG[vv]--;
  40.                 if (OUTDEG[vv] == 0) {
  41.                     Q.push(vv);
  42.                 }
  43.             }
  44.             u[v] = 1;
  45.         }
  46.         for (int i = (int)RR.size()-1; i >= 0; i--) {
  47.             R.push_back(RR[i]);
  48.         }
  49.         while (u[cur]) cur++;
  50.     }
  51.     for (int i = 0; i < n; i++) {
  52.         cout << R[i]+1 << " " ;
  53.     }
  54.     cout << endl;
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment