Advertisement
MinhNGUYEN2k4

Untitled

Nov 14th, 2021
899
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n;
  28. int vst[100005];
  29. vector<int> g[100005];
  30. vector<ii> cycle;
  31. bool flag[100005];
  32. int par[100005];
  33.  
  34. void readfile()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0);cout.tie(0);
  38.     if (fopen(Task".inp","r"))
  39.     {
  40.         freopen(Task".inp","r",stdin);
  41.         //freopen(Task".out","w",stdout);
  42.     }
  43.     cin >> n;
  44. }
  45.  
  46. void dfs(int u){
  47.     flag[u] = 1;
  48.     for(auto v : g[u]){
  49.         if (!flag[v]){
  50.             par[v] = u;
  51.             dfs(v);
  52.         }
  53.         else if (flag[v] && v==0){
  54.             par[v] = u;
  55.             cycle.pb(ii(v,u));
  56.         }
  57.     }
  58.     flag[u] = 0;
  59. }
  60.  
  61. void proc()
  62. {
  63.     for(int i=0; i<n; i++){
  64.         int u = (2*i)%n;
  65.         g[i].pb(u);
  66.         int v = (2*i+1)%n;
  67.         g[i].pb(v);
  68.         //cout << u << ' ' << v << endl;
  69.     }
  70.     for(int i=0; i<n; i++){
  71.         for(auto x : g[i]){
  72.             //cout << i << ' ' << x << '\n';
  73.         }
  74.     }
  75.     dfs(0);
  76.     for(auto x : cycle){
  77.         if (x.fi==0 && x.se==0){
  78.             stack<int> st;
  79.             int cur = 0;
  80.             st.push(0);
  81.             while (par[cur]!=0){
  82.                 st.push(par[cur]);
  83.                 cur = par[cur];
  84.             }
  85.             st.push(0);
  86.             while (st.size()){
  87.                 cout << st.top() << ' ';
  88.                 st.pop();
  89.             }
  90.         }
  91.     }
  92. }
  93.  
  94. signed main()
  95. {
  96.     readfile();
  97.     proc();
  98.     return 0;
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement