bhupixb

Detecting cycle using DFS

Jun 29th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.81 KB | None | 0 0
  1. /*
  2. I am Hunting High and Low
  3. Diving from the sky above
  4. Looking for, more and more, once again
  5. I'm Hunting High and Low
  6. Sometimes I may win, sometimes I'll lose
  7. It's just a game that I play
  8.  
  9. After the storm there's a calm
  10. Through the clouds shines a ray of the sun
  11. I'm carried from all my harm
  12. There is no one I can't outrun
  13.  
  14. Now I'm leaving my worries behind
  15. Feel the freedom of body and mind
  16. I'm starting my journey, I'm drifting away with the wind, I go___________________:-
  17. */
  18.  
  19. #include <bits/stdc++.h>
  20. using namespace std;
  21. /* #include <ext/pb_ds/assoc_container.hpp>
  22. using namespace __gnu_pbds;
  23. typedef tree<int,null_type,less<int>,rb_tree_tag,
  24. tree_order_statistics_node_update> indexed_set; */
  25.  
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28. typedef long double ld;
  29. typedef pair < int , int > pi;
  30. typedef pair < int64_t , int64_t > pii;
  31. const int N = 1e5+7;
  32.  
  33. int luck[N], vis[N];
  34. const int32_t mod = 1e9 + 7;
  35.  
  36.  
  37. #define pb(x) push_back(x)
  38. #define A(s) s.begin(),s.end()
  39. #define L(x) (int)((x).size())
  40. #define V vector<int>
  41. #define VL vector<ll>
  42. #define S set<int>
  43. #define SL set<ll>
  44. #define Ml multiset < int >
  45. #define ML multiset < ll >
  46. #define f(i,p,n) for(int i=(p);i<n;i++)
  47. #define B(v) v.begin()
  48. #define E(v) v.end()
  49. #define M map < int , int >
  50. #define SS second
  51. #define F first
  52. vector < V > v(N);
  53.  
  54. template <class T> inline void smax(T &x,T y){ x = max((x), (y));}
  55. template <class T> inline void smin(T &x,T y){ x = min((x), (y));}
  56. void initializer(int n, int x = 1){
  57. if(x > n)return;
  58. luck[x] = 100;
  59. initializer(n, x + 1);
  60. }
  61. int flag = 0;
  62. // to detect a cycle using dfs
  63. void Eminem_Lover(int to_p, int check){
  64. vis[to_p] = true;
  65. for(auto it : v[to_p]){
  66. if(!vis[it]){
  67. Eminem_Lover(it, to_p);
  68. }
  69. else if(vis[it] && it != check)flag = 1;//Cycle detected
  70. }// check ki condition mandatory h ........... otherwise Jaha se call aayi h usi ko manke cycle bataa dega
  71. }
  72.  
  73. ll expo(ll x, ll n, ll mod){
  74. ll res = 1LL;
  75. while(n){
  76. if(n & 1) res = (res * x) % mod;
  77. x = (x * x) % mod;
  78. n = n / 2;
  79. }
  80. return res;
  81. }
  82. int main(){
  83. ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  84. #ifndef ONLINE_JUDGE
  85. // freopen("in.txt", "r", stdin);
  86. // freopen("out.txt", "w", stdout);
  87. #endif
  88. int i, j, k, l, r, cnt1 = 0, cnt2 = 0;
  89. // Begin:-
  90. int n;
  91. cin >> n;
  92.  
  93. f(i,0,n-1)cin >> l >> r, v[l].pb(r), v[r].pb(l);
  94. initializer(n);
  95. Eminem_Lover(3, 3);// Kisi b root ki adjacancy list me vahi element to present hoga nahi
  96. // isliye for first time Root ko hi check banaa k bhej diya h
  97. // Ho skta h glt ho logic.............. mgr lg to theek hi rha h
  98. cout << flag;
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106. return 0;
  107. }
Add Comment
Please, Sign In to add comment