Advertisement
Guest User

Untitled

a guest
May 27th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. //
  2. // Created by Henrique Navarro on 27/05/2018.
  3. //
  4. #include <bits/stdc++.h>
  5. #define ll long long int
  6. #define cl(x, v) memset((x), (v), sizeof(x))
  7.  
  8. using namespace std;
  9.  
  10. const int N = 2e3+5;
  11.  
  12. set <int> adj[N];
  13. int inc[N];
  14. queue <int> q;
  15. vector <int> khan;
  16. int n, e, a, b;
  17. int main () {
  18.     while(~scanf("%d%d", &n, &e) && n && e) {
  19.  
  20.         khan.clear();
  21.         cl(inc,0);
  22.         for (int i = 0; i < N; i++) adj[i].clear();
  23.  
  24.         for (int i = 0; i < e; i++) {
  25.             scanf("%d%d", &a, &b);
  26.             if(!adj[a].count(b)) {
  27.                 adj[a].insert(b);
  28.                 inc[b]++;
  29.             }
  30.         }
  31.         for (int i = 1; i <= n; ++i) if (inc[i] == 0) q.push(i);
  32.         while (!q.empty()) {
  33.             int u = q.front();
  34.             q.pop();
  35.             khan.push_back(u);
  36.             for (int v : adj[u])
  37.                 if (inc[v] > 0 and --inc[v] == 0)
  38.                     q.push(v);
  39.         }
  40.  
  41.         for (int i = 0; i < khan.size(); i++) printf("%d%c", khan[i], " \n"[i==khan.size()-1]);
  42.  
  43.     }
  44.     return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement