Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <deque>
- #include <stack>
- using namespace std;
- vector< deque< int > > theGraph;
- vector< deque< int > > theTransposedGraph;
- stack< int > bfsOrder;
- int visited[ 1001 ];
- inline void initCase( int n ){
- for( int i = 1; i <= n; i++ ){
- theGraph[ i ].clear();
- theTransposedGraph[ i ].clear();
- visited[ i ] = 0;
- }
- }
- void bfs( int node ){
- if( visited[ node ] ) return;
- visited[ node ] = 1;
- for( deque< int >::iterator it = theGraph[ node ].begin(); it != theGraph[ node ].end(); ++it ){
- bfs( *it );
- }
- bfsOrder.push( node );
- }
- void bfsTransposed( int node, int componentCount ){
- if( visited[ node ] ) return;
- visited[ node ] = componentCount;
- for( deque< int >::iterator it = theTransposedGraph[ node ].begin(); it != theTransposedGraph[ node ].end(); ++it ){
- bfsTransposed( *it, componentCount );
- }
- }
- int outDegree[ 1001 ];
- inline int getUniqueSinkSize( int n, int componentCount ){
- int i, zeros = componentCount;
- for( i = 1; i <= componentCount; i++ ){
- outDegree[ i ] = 0;
- }
- for( i = 1; i <= n; i++ ){
- for( deque< int >::iterator it = theGraph[ i ].begin(); it != theGraph[ i ].end(); ++it ){
- if( visited[ i ] == visited[ *it ] ) continue;
- if( 0 == ( outDegree[ visited[ i ] ]++ ) ) zeros--;
- }
- }
- if( zeros != 1 ) return 0;
- for( i = 1; i <= componentCount; i++ ) if( outDegree[ i ] == 0 ) {
- int result = 0;
- for( zeros = 1; zeros <= n; zeros++ ){
- if( visited[ zeros ] == i ) result++;
- }
- return result;
- }
- }
- int main( int argc, char* argv[] ){
- int t, n, i, j, k;
- theGraph.resize( 1001 );
- theTransposedGraph.resize(1001);
- 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 ].push_back( j );
- theTransposedGraph[ j ].push_back( i );
- }
- }
- for( i = 1; i <= n; i++ ){
- bfs( i );
- }
- for( i = 1; i <= n; i++ ){ visited[i] = 0;}
- j = 0;
- while( !bfsOrder.empty() ){
- if( !visited[ bfsOrder.top() ] ){
- j++;
- bfsTransposed( bfsOrder.top(), j );
- }
- bfsOrder.pop();
- }
- printf("%d\n",getUniqueSinkSize( n, j ) );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment