Advertisement
Guest User

Untitled

a guest
Nov 17th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <iostream>
  2. #include "stdio.h"
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int MAXN=100000;
  7. vector <vector <int> > v;
  8. short int was[MAXN];
  9. int k=-1;
  10. bool a=0;
  11. //vector<int> ans;
  12.  
  13. void dfs(int u){
  14.     was[u]=1;
  15.     //cerr<< u + 1 << "\n";
  16.     for (int j=0; j<(int)v[u].size()&&!a; j++){
  17.         if (was[v[u][j]]==1){
  18.             a=1;
  19.             cout << "YES" << "\n";
  20.             k=v[u][j];
  21.             v.clear();
  22.             v.resize(1);
  23.         }
  24.         else
  25.         {
  26.             //cerr<< u+1<<" -> "<< v[u][j]+1<<"\n";
  27.             dfs(v[u][j]);
  28.         }
  29.     }
  30.     if (a && k!=-1)
  31.     {
  32.         if(u==k) k=-1;
  33.         v[0].push_back(u+1);
  34.     }
  35.     was[u]=2;
  36. }
  37.  
  38. int main(){
  39.     freopen("cicle.in", "r", stdin);
  40.     freopen("cicle.out", "w", stdout);
  41.     int n, m;
  42.     cin >> n >> m;
  43.     v.resize(n);
  44.     for (int i=0, a, b; i<m; i++){
  45.         cin >> a >> b;
  46.         v[a-1].push_back(b-1);
  47.     }
  48.     for (int i=0; i<n; i++){
  49.         if (was[i]==0){
  50.             dfs(i);
  51.         }
  52.         if (a) break;
  53.     }
  54.     if (!a) { cout << "NO";return 0;}
  55. //  if (ans.size()==0){ cout << "NO"; return 0;}
  56. //  cout << k << " ";
  57. //  cout << ans.size() << " "<< ans[ans.size()-1]<< " ";
  58.     for (int i=v[0].size()-1; i>=0; i--){
  59.         cout << v[0][i] << " ";
  60.     }
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement