Poj Solution 2890

http://poj.org/problem?id=2890

#include <functional>
//#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

vector<int> e[1000];
stack<int> sk;

int sign[1000] = { 0 };
int count = 0;
int c;

int n, m;
bool input() {
    int i, a, b;
    if( scanf( "%d%d", &n, &m ) != 2 )
        return false;
        
    for( i=0; i<n; i++ ) {
        e[i].clear( );
    }
    
    for( i=0; i<m; i++ ) {
        scanf( "%d%d", &a, &b );
        e[a].push_back( b );
    }
    return true;
}

void travel( int k ) {
    int i;
    c++;
    sign[k] = count;
    for( i=0; i<e[k].size(); i++ )
        if( sign[ e[k][i] ] != count )
            travel( e[k][i] );
        
} 
        

int doit() {
    int ans = 0, i;
    for( i=0; i<n; i++ ) {
        count++;
        c=0;
        travel( i );
        ans += c;
    }
    return ans;
}

int main( ) {
    while( input() ) {
        printf( "%dn", doit() );
    }
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *