Ankit_132

C

Jul 22nd, 2023
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll     long long
  7. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  8. #define ff     first
  9. #define ss     second
  10. #define pb     push_back
  11. #define ppb    pop_back
  12.  
  13. int main()
  14. {
  15.     int n;
  16.     cin>>n;
  17.  
  18.     vector<vector<int>> graph(n);
  19.  
  20.     for(int i=0; i<n; i++)
  21.     {
  22.         int v;
  23.         cin>>v;
  24.  
  25.         v--;
  26.  
  27.         graph[i].pb(v);
  28.     }
  29.  
  30.     vector<int> vis(n);
  31.     vector<int> prev(n, -1);
  32.  
  33.     function<void(int)> DFS = [&](int u)
  34.     {
  35.         vis[u] = 1;
  36.  
  37.         for(auto v: graph[u])
  38.         {
  39.             if(!vis[v])
  40.             {
  41.                 prev[v] = u;
  42.                 DFS(v);
  43.             }
  44.             else
  45.             {
  46.                 vector<int> ans;
  47.  
  48.                 int x = u;
  49.                 while(x != v)
  50.                 {
  51.                     ans.pb(x+1);
  52.                     x = prev[x];
  53.                 }
  54.  
  55.                 ans.pb(v+1);
  56.  
  57.                 reverse(ans.begin(), ans.end());
  58.  
  59.                 cout<<ans.size()<<"\n";
  60.                 for(auto e: ans)        cout<<e<<" ";
  61.                 cout<<"\n";
  62.                 exit(0);
  63.             }
  64.         }
  65.  
  66.         vis[u] = 2;
  67.     };
  68.  
  69.     for(int i=0; i<n; i++)
  70.     {
  71.         if(!vis[i])
  72.             DFS(i);
  73.     }
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment