TOUR v2

#include <stdio.h>
#include <string.h>

int theGraph[1001][1001];
int theTransposedGraph[1001][1001];
int degreeG[1001];
int degreeTG[1001];

int bfsOrder[ 1001 ];
int bfsSp;

int visited[ 1001 ];
int sizes[ 1001 ];

inline void initCase( int n ){
  memset( degreeG, 0, sizeof(int)*(n+1));
  memset( degreeTG, 0, sizeof(int)*(n+1));
  memset( visited, 0, sizeof(int)*(n+1));
  bfsSp = 0;
}

void bfs( int node ){
  if( visited[ node ] ) return;
  visited[ node ] = 1;
  for( int i = 0; i < degreeG[ node ]; i++ ){ bfs(theGraph[node][i]); }
  bfsOrder[ bfsSp++ ] = node;
}

void bfsTransposed( int node, int componentCount ){
  if( visited[ node ] ) return;
  visited[ node ] = componentCount;
  sizes[ componentCount ]++;
  for( int i = 0; i < degreeTG[ node ]; i++ ){
    bfsTransposed( theTransposedGraph[node][i], componentCount );
  }
}

int outDegree[ 1001 ];
inline int getUniqueSinkSize( int n, int componentCount ){
  int i, zeros = componentCount;
  memset( outDegree, 0, sizeof( int)*(componentCount+1) );
  for( i = 1; i <= n; i++ ){
    if( outDegree[ visited[ i ] ] ) continue;
    for( int j = 0; j < degreeG[i]; j++ ){
      if( visited[ i ] == visited[ theGraph[i][j] ] ) continue;
      if( 0 == ( outDegree[ visited[ i ] ]++ ) ) { zeros--; break ; }
    }
  }
  if( zeros != 1 ) return 0;
  for( i = 1; i <= componentCount; i++ ) if( outDegree[ i ] == 0 ) {
    return sizes[ componentCount ];
  }
}

int main( int argc, char* argv[] ){
  int t, n, i, j, k;
  scanf("%d",&t);
  while( t-- ){
    scanf("%d",&n);
    initCase( n );
    for( i = 1; i <= n; i++ ){
      scanf("%d",&k);
      while( k-- ){
        scanf("%d",&j);
        theGraph[i][ degreeG[i]++ ] = j;
        theTransposedGraph[j][ degreeTG[j]++ ] = i;
      }
    }
    for( i = 1; i <= n; i++ ){
      bfs( i );
    }
    memset( visited, 0, sizeof(int)*(n+1) );
    j = 0;
    while( bfsSp ){
      if( !visited[ bfsOrder[ bfsSp - 1 ] ] ){
        j++;
        sizes[ j ] = 0;
        bfsTransposed( bfsOrder[ bfsSp - 1 ], j );
      }
      bfsSp--;
    }
    printf("%d\n",getUniqueSinkSize( n, j ) );
  }
  return 0;
}