fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #pragma comment(linker, "/stack:200000000")
  4. #define ll long long int
  5. #define inf ( int )( 1e9 + 1e9 )
  6. #define mxs (int)( 1e6 + 10 )
  7. #define md  int mid = ( l + r )>>1;
  8. #define mod 10000000000007//(ll)(1e9)+7
  9. //int dx[]={+1,0,+0,-1};///Four Directions
  10. //int dy[]={+0,-1,+1,+0};///Four directions
  11. //int dx [] = {+1,-1,+0,+0,-1,-1,+1,+1};///Eight Directions
  12. //int dy [] = {+0,+0,+1,-1,+1,-1,-1,+1};///Eight Directions
  13. int t, n, m, j,a, b, c, d, e,f, i,ans,cases , pos , num , root;
  14. string s, s2, s3, s4;
  15. int visited [ 510 ] , level [ 510 ] , parent [ 510 ];
  16. queue < int > qu;
  17. vector < int > graph [ mxs ];
  18. void brainfuck();
  19. int finder( int node );
  20. int main()
  21. {
  22.     //freopen("input.txt","r",stdin);
  23.     //freopen("output.txt","w",stdout);
  24.     ios_base::sync_with_stdio(false);
  25.     cin.tie(NULL);
  26.     cout.tie(NULL);
  27.     brainfuck();
  28.     return 0;
  29. }
  30. void brainfuck()
  31. {
  32.     cin>>t;
  33.     while( t-- )
  34.     {
  35.         cin>>n>>m;
  36.         for ( i = 0 ; i <= n; i++ )
  37.         {
  38.             graph [ i ].clear();
  39.         }
  40.         while( m-- )
  41.         {
  42.             cin>>a>>b;
  43.             graph [ a ].push_back( b );
  44.             graph [ b ].push_back( a );
  45.         }
  46.         ans = inf;
  47.         for ( i = 0; i < n; i++ )
  48.         {
  49.             ans = min( ans , finder( i ) );
  50.         }
  51.         cout<<"Case "<<++cases<<": ";
  52.         if ( ans == inf )cout<<"impossible\n";
  53.         else cout<<ans<<"\n";
  54.     }
  55. }
  56. int finder( int node )
  57. {
  58.     int lol = inf;
  59.     while( !qu.empty() )qu.pop();
  60.     memset( visited , 0 , sizeof visited );
  61.     memset( parent , -1, sizeof parent );
  62.     level [ node ] = 0;
  63.     qu.push( node );
  64.     visited [ node ] = 1;
  65.     while( !qu.empty() )
  66.     {
  67.         a = qu.front();
  68.         qu.pop();
  69.         int sz = graph [ a ].size();
  70.         for ( j = 0 ; j < sz; j++ )
  71.         {
  72.             b = graph [ a ] [ j ];
  73.             if ( !visited [ b ] )
  74.             {
  75.                 parent [ b ] = a;
  76.                 qu.push( b );
  77.                 level [ b ] = level [ a ] + 1;
  78.                 visited [ b ] = 1;
  79.             }
  80.             else if ( parent [ a ] != b )
  81.             {
  82.                 lol = min( lol , level [ a ] + level [ b ] + 1 );
  83.                 //return ( level [ a ] + level [ b ] + 1);
  84.             }
  85.         }
  86.     }
  87.     return lol;
  88. }
Success #stdin #stdout 0.01s 27100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/duuUe9
language:
C++14 (gcc 8.3)
created:
4 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!