#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cmath>

#define maxn 10001
#define maxm 50001
using namespace std;

int y[maxm],now[maxn],pre[maxm],tot,LOW[maxn],DFN[maxn],stack[maxn],Belong[maxn],k,Sum;
int outdegree[maxn],step,Cnt,top,N,M;
bool visit[maxn];

void addedge(int from , int to){
     tot++;
     pre[tot] = now[from] ;
     now[from] = tot ;
     y[tot] = to;
}
void tarjan(int u){
     DFN[u] = LOW[u] = ++step ;
     visit[u] = 1;
     stack[++top] = u ;
     for (int mark = now[u] ; mark > 0 ; mark = pre[mark])
        {
            int v = y[mark];
            if (!DFN[v])
                {
                    tarjan(v);
                    LOW[u] = min(LOW[u],LOW[v]);
                }
            else
                {
                    if (visit[v])
                        LOW[u] = min(LOW[u],DFN[v]);
                }
        }
     if (LOW[u] == DFN[u])
        {
            Cnt++;
            int v;
            do
            {
                v = stack[top--];
                Belong[v] = Cnt;
                visit[v] = false;
            }
            while (v!=u);
        }
}
void initialize(){
    scanf("%d%d",&N,&M);
    tot = 0 ;
    for (int i = 1 ; i <= M ; i++)
        {
            int A , B;
            scanf("%d%d",&A,&B);
            addedge(A , B);
        }
    /*for (int i = 1 ; i <= N ; i++)
        {
            for (int mark = now[i] ; mark > 0 ; mark = pre[mark])
                {
                    int j = y[mark];
                    printf("%d ",j);
                }
            printf("\n");
        }*/
    }
void solve(){
    memset(DFN,0,sizeof(DFN));
    memset(visit,false,sizeof(visit));
    step = top = Cnt = 0 ;
    for (int i = 1 ; i <= N ; i++)
        if (!DFN[i])
            tarjan(i);
    memset(outdegree,0,sizeof(outdegree));
    for (int i = 1 ; i <= N ; i++)
        {
            for (int mark = now[i] ; mark > 0 ; mark = pre[mark])
                {
                    int j = y[mark];
                    if (Belong[i]!=Belong[j])
                        outdegree[Belong[i]]++;
                }
        }
    //for (int i = 1 ; i <= N ; i++)
    //    printf("%d\n",Belong[i]);
   // printf("%d\n",Cnt);
    Sum = 0 ;
    for (int i = 1 ; i <= Cnt ; i++)
        if (outdegree[i] == 0)
            {
                    Sum++;
                    k = i ;
            }
   // printf("%d\n",Sum);
    }
void outitialize(){
    if (Sum != 1)
        {
            printf("%d\n",0);
            exit(0);
        }
    int Answer = 0 ;
    for (int i = 1 ; i <= N ; i++)
        if (Belong[i] == Cnt)
            {
                Answer++;
            }
    printf("%d\n",Answer);
    }
int main(){
    //freopen("tmp.in","r",stdin);
    //freopen("tmp1.out","w",stdout);
    int t ;
    t = 1;
    while (t--)
        {
            initialize();
            solve();
            outitialize();
        }
    return 0;
    }

• Re:不知道为什么WA.和正确程序跑了100多组数据依然一致 (2640) SunnyElemeNt 2010-05-31 15:09:38