Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 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. vector<int> ans;
  14.  
  15. int mark[MAX];
  16. int n, m;
  17.  
  18. bool dfs(int v) {
  19. if (mark[v] != 0) return 0;
  20. mark[v] = 1;
  21. for( int x : graph[v]) {
  22. dfs(x);
  23. if (mark[x] == 1)
  24. return 1;
  25. }
  26. oto.push_back(v);
  27. mark[v] = 2;
  28. return false;
  29. }
  30.  
  31. void top_sort() {
  32. forn(i, n)
  33. mark[i] = 0;
  34. oto.clear();
  35. forn(i, n)
  36. if(!mark[i]) {
  37. if (dfs(i) == 1) {
  38. cout << "NO" << "\n";
  39. return;
  40. }
  41. }
  42. reverse(oto.begin(), oto.end());
  43. for(int i: oto) {
  44. if (*graph[i].find(i + 1)) {
  45. ans.push_back(i);
  46. for (int i: ans)
  47. cout << i << " ";
  48. return;
  49. } else
  50. {
  51. cout << "NO" << "\n";
  52. return;
  53. }
  54.  
  55. }
  56. }
  57.  
  58. int main() {
  59. ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  60. cin >> n >> m;
  61.  
  62. int u, v;
  63. forn(i, m) {
  64. cin >> v >> u;
  65. graph[v].insert(u);
  66. }
  67. top_sort();
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement