szabivan

TOUR

Oct 22nd, 2013
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <deque>
  4. #include <stack>
  5.  
  6. using namespace std;
  7.  
  8. vector< deque< int > > theGraph;
  9. vector< deque< int > > theTransposedGraph;
  10. stack< int > bfsOrder;
  11. int visited[ 1001 ];
  12.  
  13. inline void initCase( int n ){
  14.   for( int i = 1; i <= n; i++ ){
  15.     theGraph[ i ].clear();
  16.     theTransposedGraph[ i ].clear();
  17.     visited[ i ] = 0;
  18.   }  
  19. }
  20.  
  21. void bfs( int node ){
  22.   if( visited[ node ] ) return;
  23.   visited[ node ] = 1;
  24.   for( deque< int >::iterator it = theGraph[ node ].begin(); it != theGraph[ node ].end(); ++it ){
  25.     bfs( *it );
  26.   }
  27.   bfsOrder.push( node );
  28. }
  29.  
  30. void bfsTransposed( int node, int componentCount ){
  31.   if( visited[ node ] ) return;
  32.   visited[ node ] = componentCount;
  33.   for( deque< int >::iterator it = theTransposedGraph[ node ].begin(); it != theTransposedGraph[ node ].end(); ++it ){
  34.     bfsTransposed( *it, componentCount );
  35.   }
  36. }
  37.  
  38. int outDegree[ 1001 ];
  39. inline int getUniqueSinkSize( int n, int componentCount ){
  40.   int i, zeros = componentCount;
  41.   for( i = 1; i <= componentCount; i++ ){
  42.     outDegree[ i ] = 0;
  43.   }
  44.   for( i = 1; i <= n; i++ ){
  45.     for( deque< int >::iterator it = theGraph[ i ].begin(); it != theGraph[ i ].end(); ++it ){
  46.       if( visited[ i ] == visited[ *it ] ) continue;
  47.       if( 0 == ( outDegree[ visited[ i ] ]++ ) ) zeros--;      
  48.     }
  49.   }
  50.   if( zeros != 1 ) return 0;
  51.   for( i = 1; i <= componentCount; i++ ) if( outDegree[ i ] == 0 ) {
  52.     int result = 0;
  53.     for( zeros = 1; zeros <= n; zeros++ ){
  54.       if( visited[ zeros ] == i ) result++;
  55.     }
  56.     return result;
  57.   }
  58. }
  59.  
  60. int main( int argc, char* argv[] ){
  61.   int t, n, i, j, k;
  62.   theGraph.resize( 1001 );
  63.   theTransposedGraph.resize(1001);
  64.   scanf("%d",&t);
  65.   while( t-- ){
  66.     scanf("%d",&n);
  67.     initCase( n );
  68.     for( i = 1; i <= n; i++ ){
  69.       scanf("%d",&k);
  70.       while( k-- ){
  71.         scanf("%d",&j);
  72.         theGraph[ i ].push_back( j );
  73.         theTransposedGraph[ j ].push_back( i );
  74.       }
  75.     }
  76.     for( i = 1; i <= n; i++ ){
  77.       bfs( i );
  78.     }
  79.     for( i = 1; i <= n; i++ ){ visited[i] = 0;}
  80.     j = 0;
  81.     while( !bfsOrder.empty() ){
  82.       if( !visited[ bfsOrder.top() ] ){
  83.         j++;
  84.         bfsTransposed( bfsOrder.top(), j );
  85.       }
  86.       bfsOrder.pop();
  87.     }
  88.     printf("%d\n",getUniqueSinkSize( n, j ) );
  89.   }
  90.   return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment