#include <iostream>
using namespace std;
struct edge
{
int v,next;
};
edge grap[60005];
edge grapt[61005];
int cnt;
int n,m;
bool visit[10005];
int finish[10005], id;
int grp[10005], g;
int outdegree[10005];
void add(int u, int v)
{
grap[cnt].v=v;
grap[cnt].next=grap[u].next;
grap[u].next=cnt;
grapt[cnt].v=u;
grapt[cnt].next=grapt[v].next;
grapt[v].next=cnt;
cnt++;
}
void dfs(int u)
{
int p;
visit[u]=1;
p=grap[u].next;
while(p)
{
if(!visit[grap[p].v])
dfs(grap[p].v);
p=grap[p].next;
}
finish[++id]=u;
}
void dfst(int u)
{
int p;
visit[u]=1;
p=grapt[u].next;
grp[u]=g;
while(p)
{
if(!visit[grapt[p].v])
dfst(grapt[p].v);
p=grapt[p].next;
}
}
void scc()
{
int i;
g=0,id=0;
memset(visit, 0, sizeof(visit));
for(i=1; i<=n; i++)
if(!visit[i])
dfs(i);
memset(visit, 0, sizeof(visit));
for(i=n; i>0 ; --i)
{
if(!visit[finish[i]])
{
g++;
dfst(finish[i]);
}
}
}
void solve()
{
int i,j, p, tmp;
memset(outdegree, 0, sizeof(outdegree));
for(i=1; i<=n; i++)
{
p=grap[i].next;
while(p)
{
if(grp[i]!=grp[ grap[p].v])
++outdegree[grp[i]];
p=grap[p].next;
}
}
for(i=1, tmp=0; i<=g; i++)
{
//printf("%d %d\n", i, outdegree[i]);
if(outdegree[i] == 0)
{
++tmp, j=i;
}
}
//printf("%d %d\n", tmp, j);
if(tmp!=1) // >1 || 0
{
printf("0\n");
}
else
{
tmp=0;
for(i=1; i<=n; i++)
if(grp[i]== j )
tmp++;
printf("%d\n", tmp);
}
}
int main()
{
int i, j, u, v;
while(scanf("%d%d",&n, &m)!=EOF)
{
cnt=n+1;
memset(grap, 0, sizeof(grap));
memset(grapt, 0, sizeof(grapt));
for(i=0; i<m; i++)
{
scanf("%d%d", &u, &v);
add(u, v);
}
scc();
solve();
}
return 0;
}
posted on 2010-03-25 16:28
wyiu 閱讀(229)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ