fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6.  
  7. " when you are not practicing someone else is ,
  8.  and the day u meet them u will lose "
  9.  
  10. */
  11. #include<bits/stdc++.h>
  12. #include<stdio.h>
  13. using namespace std;
  14.  
  15. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  16. #define MAX 200050
  17.  
  18. #define ll long long
  19. #define ld long double
  20. #define lli long long int
  21.  
  22. #define pb push_back
  23. #define INF 1000000000000
  24. #define mod 1000000007
  25.  
  26. // trignometric function always give value in Radians only
  27. #define PI acos(-1) //3.1415926535897932384626433832795028
  28. #define dsin(degree) sin(degree*(PI/180.0))
  29. #define dcos(degree) cos(degree*(PI/180.0))
  30. #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32. #define rsin(radian) sin(radian)
  33. #define rcos(radian) cos(radian)
  34. #define rtan(radian) tan(radian)
  35.  
  36. #define mem0(a) memset(a,0,sizeof(a))
  37. #define mem1(a) memset(a,-1,sizeof(a))
  38. #define memf(a) memset(a,false,sizeof(a))
  39.  
  40. #define loop(i,n)  for (lli i = 0; i < n; i++)
  41. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  42.  
  43. #define all(v) v.begin(),v.end()
  44. #define rall(v) v.rbegin(),v.rend()
  45. #define sz(x) int(x.size())
  46. #define F first
  47. #define S second
  48.  
  49. #define mii map<lli,lli>
  50.  
  51. #define pii pair<lli,lli>
  52.  
  53. #define vi vector<lli>
  54. #define vvi vector<vi>
  55. #define vpi vector<pii>
  56. #define vbool vector<bool>
  57.  
  58. #define seti set<lli>
  59.  
  60. #define gcd(a,b) __gcd((a),(b))
  61. #define lcm(a,b) (a/gcd(a,b))*b
  62. #define abs(x) ((x < 0)?-(x):x)
  63.  
  64. #define endl '\n'
  65.  
  66. template <typename T>
  67. void print(T x){cout<<x<<endl;}
  68. template <typename T1, typename T2>
  69. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  70. template <typename T1, typename T2,typename T3>
  71. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  72.  
  73. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  74. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  75.  
  76. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  77. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  78.  
  79. #define FD(N) fixed<<setprecision(N)
  80.  
  81. #define deb(x) cout<<#x<<" "<<x<<endl;
  82.  
  83. /*
  84. 1D vector -  vi dp(n,value);
  85. 2D vector -  vvi dp(n,vi(n,value));
  86. */
  87.  
  88. // chandan1,2
  89. void chandan1(){int y=1;return;}
  90. void chandan2(){
  91.         loop(i,10){
  92.         lli x=1;
  93.     }
  94.     return(chandan1());
  95. }
  96.  
  97. vi adj[MAX];
  98.  
  99. // minimum length cycle in graph -
  100. lli bfs(lli src , lli n)
  101. {
  102.     lli res = INF;
  103.  
  104.     vi dist(n+1 , INF);
  105.     vi parent(n+1,-1);
  106.  
  107.     queue<lli>q;
  108.     q.push(src);
  109.     dist[src]=0;
  110.     while(!q.empty())
  111.     {
  112.         lli u = q.front();q.pop();
  113.  
  114.         for(auto child : adj[u])
  115.         {
  116.             if(child == parent[u]) continue; // means ham node u ko hi dekh rahe hai jo ki child ka hi adjacent hai
  117.  
  118.             if(dist[child] == INF ) // means they are unvisited
  119.             {
  120.                 dist[child] = dist[u]+1;
  121.                 q.push(child);
  122.                 parent[child] = u;
  123.             }
  124.             else
  125.             {
  126.                 // means there is a cycle;
  127.  
  128.                 //The to vertex has already been visited. Loop found. There is a path from start to u of length d [ u ] and from start to to of length d [ to ].
  129.                 //At the moment we have met an edge ( u , to ) forming a cycle. The cycle length is d [ to ] + d [ u ] + 1 
  130.                 res = min(res , (dist[u] + dist[child] +1 ));
  131.  
  132.                 if(res == 3)
  133.                     return 3; //If the length of the cycle has become equal to 3, then it can no longer decrease.
  134.             }
  135.         }
  136.     }
  137.     return res;
  138. }
  139.  
  140. int main(){
  141. fastio
  142. lli t=1;
  143. cin>>t;
  144. chandan2();
  145. loop(qw,t) {
  146.     cout<<"Case "<<qw+1<<": ";
  147.     lli n,m;
  148.  
  149.     cin>>n>>m;
  150.  
  151.     loop(i,m)
  152.     {
  153.         lli x,y;
  154.         cin>>x>>y;
  155.         adj[x+1].pb(y+1);
  156.         adj[y+1].pb(x+1);
  157.     }
  158.  
  159.     lli ans = INF;
  160.  
  161.     FOR(i,1,n+1)
  162.     {
  163.         ans = min(ans , bfs(i,n));
  164.         if(ans == 3)
  165.             break;
  166.     }
  167.  
  168.     if(ans == INF)
  169.         print("impossible");
  170.     else
  171.         print(ans);
  172.  
  173.     FOR(i,1,n+1)
  174.         adj[i].clear();
  175.   }
  176. return 0;
  177. }
  178.  
Success #stdin #stdout 0s 8172KB
comments (?)
stdin
copy 
3

3 3
0 1
1 2
2 0

2 1
0 1

5 6
0 1
1 2
1 3
2 3
0 4
3 4
stdout
copy 
Case 1: 3
Case 2: impossible
Case 3: 3
https://ideone.com/hjaBe1
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!