fork download
  1. /*
  2.   Copyright 2011 Marek "p2004a" Rusinowski
  3.   Kahn algorithm
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <queue>
  8.  
  9. #define MAXN 1000000
  10.  
  11. std::vector<int> edges[MAXN];
  12. int indeg[MAXN];
  13.  
  14. int main() {
  15. int a, b, n, m;
  16. scanf("%d %d", &n, &m);
  17. for (int i = 0; i < m; ++i) {
  18. scanf("%d %d", &a, &b);
  19. edges[--a].push_back(--b);
  20. ++indeg[b];
  21. }
  22. std::queue<int> q;
  23. for (int i = 0; i < n; ++i) {
  24. if (!indeg[i]) {
  25. q.push(i);
  26. }
  27. }
  28. while (!q.empty()) {
  29. int v = q.front();
  30. printf("%d ", v + 1);
  31. q.pop();
  32. for (unsigned i = 0; i < edges[v].size(); ++i) {
  33. --indeg[edges[v][i]];
  34. if (!indeg[edges[v][i]]) {
  35. q.push(edges[v][i]);
  36. }
  37. }
  38. }
  39. printf("\n");
  40. return 0;
  41. }
  42.  
stdin
6 6
1 2
2 4
2 5
4 5
3 6
2 6
compilation info
prog.cpp: In function ‘int main()’:
prog.cpp:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
1 3 2 4 6 5