Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. #define forn(i, n) for(int i = 1; i <= n; ++i)
  7. #define MAX 100002
  8.  
  9. using namespace std;
  10.  
  11. vector<set<int>>graph(MAX);
  12. vector<int>oto;
  13.  
  14. int mark[MAX];
  15. int n, m;
  16.  
  17. void dfs(int v) {
  18. mark[v] = 1;
  19. for( int x : graph[v]) {
  20. if (mark[x] == 0)
  21. dfs(x);
  22. }
  23. oto.push_back(v);
  24. }
  25.  
  26. void top_sort() {
  27. forn(i, n)
  28. mark[i] = 0;
  29. oto.clear();
  30. forn(i, n)
  31. if(!mark[i])
  32. dfs(i);
  33. reverse(oto.begin(), oto.end());
  34. for(int i: oto) {
  35. if (graph[i].find(i + 1) == graph[i].end()) {
  36. cout << "NO" << "\n";
  37. return;
  38. }
  39. }
  40. for (int i: oto) {
  41. cout << i << " ";
  42. return;
  43. }
  44. }
  45.  
  46. int main() {
  47. ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  48. cin >> n >> m;
  49.  
  50. int u, v;
  51. forn(i, m) {
  52. cin >> v >> u;
  53. graph[v].insert(u);
  54. }
  55. top_sort();
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement