Advertisement
Guest User

Untitled

a guest
Jan 19th, 2020
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MN = 100001;
  8.  
  9. int is[MN];
  10. int n;
  11. vector <vector<int>> vert(MN);
  12. int beg = -1;
  13.  
  14.  
  15. bool dfs (int v, vector <int>& ans) {
  16.     is[v] = 1;
  17.     for (int i = 0; i < vert[v].size(); i++) {
  18.         if (is[vert[v][i]] == 0) {
  19.             if (dfs(vert[v][i], ans))
  20.                 return true;
  21.         }
  22.         else if (is[vert[v][i]] == 1) {
  23.             beg = vert[v][i];
  24.             return true;
  25.         }
  26.     }
  27.     is[v] = 2;
  28.     ans.push_back(v);
  29.     return false;
  30. }
  31.  
  32. int main() {
  33.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  34.     int m, x, y;
  35.     cin >> n >> m;
  36.     vector <int> ans;
  37.     for (int j = 0 ; j < m; j++) {
  38.         cin >> x >> y;
  39.         vert[x].push_back(y);
  40.     }
  41.     for (int i = 0; i < n; i++){
  42.         is[i] = 0;
  43.     }
  44.     for (int i = 0; i < n; i++) {
  45.         if (dfs(i, ans))
  46.             break;
  47.     }
  48.     reverse(ans.begin(), ans.end());
  49.     if (beg != -1) {
  50.         cout << -1;
  51.         return 0;
  52.     }
  53.     for (int i = 0; i < n; i++) {
  54.         cout << ans[i] << ' ';
  55.     }
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement