#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 10010
int n, m;
vector<int> mapa[MAXN], mapb[MAXN];
bool visite[MAXN];
int post[MAXN], num[MAXN],size[MAXN], in[MAXN], cnt= 0, c= 0, s= 0;
void dfs( int u )
{
visite[u]= true;
for( size_t i= 0; i< mapb[u].size(); ++i )
if( !visite[ mapb[u][i] ] ) dfs( mapb[u][i] );
post[cnt++]= u;
}
void Ddfs( int u, int id )
{
visite[u]= true;
num[u]= id; s++;
for( size_t i= 0; i< mapa[u].size(); ++i )
if( !visite[ mapa[u][i] ] )
Ddfs( mapa[u][i], id );
}
void run()
{
memset( visite, false, sizeof(visite) );
cnt= 0; c= 0;
for( int i= 1; i<= n; ++i )
if( !visite[i] ) dfs( i );
memset( visite, false, sizeof(visite) );
memset( size, 0, sizeof(size) );
for( int i= cnt- 1; i>= 0; i-- )
if( !visite[ post[i] ] )
{
s= 0;
Ddfs( post[i], ++c );
size[c]= s;
}
}
void degree()
{
memset( in, 0, sizeof(in) );
for( int i= 1; i<= n; ++i )
for( size_t j= 0; j< mapa[i].size(); ++j )
if( num[i]!= num[ mapa[i][j] ] )
in[ num[i] ]++;
int nu= 0, k;
for( int i= 1; i<= c; ++i )
if( in[i]== 0 ) k= i, nu++;
if( nu!= 1 ) puts("0");
else printf("%d\n", size[k] );
}
int main()
{
scanf("%d%d",&n,&m );
for( int i= 0; i< m; ++i )
{
int u, v;
scanf("%d%d",&u,&v );
mapa[u].push_back( v );
mapb[v].push_back( u );
}
run();
degree();
return 0;
}
posted on 2008-12-05 20:21
Darren 閱讀(423)
評(píng)論(0) 編輯 收藏 引用