POJ2186 Popular Cows

经过无数次WA的洗礼，终于得到了AC
Popular Cows
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 29828 Accepted: 12101
Description
Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
Input
* Line 1: Two space-separated integers, N and M
* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.
Output
* Line 1: A single integer that is the number of cows who are considered popular by every other cow.
Sample Input
3 3
1 2
2 1
2 3
Sample Output
1
Hint
Cow 3 is the only cow of high popularity.

附代码和注释

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#define inf 2147483640
//#define debug
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
struct Edge{
    int x;
    int y;
};
vector<int> e[1000000];
vector<int> g[1000000];
int dfn[1000000],low[1000000],stacka[1000000],inset[1000000],out[1000000],in[1000000];
Edge edge[1000000];
bool instack[1000000]={0};
int dfsnow=0,n,m,top=0,gnow=500000;
void tarjan(int a){
    if(dfn[a]==-1){//如果这个点没有被访问，则访问这个点。
        dfsnow++;
        dfn[a]=dfsnow;//将这个点对应的dfn数组设置为它的dfn
        low[a]=dfn[a];
        stacka[top]=a;
        top++;//把这个点入栈
        instack[a]=1;//标记这个点已经入栈
        inset[a]=a;//认为这个点初始处在的环即为它自己（似乎不写这一句也可以）
        for(int i=0;i<e[a].size();i++){//枚举这个点所有的出边
            int j=e[a][i];//j代表i这条边连接的点
            if(dfn[j]==-1){//如果j点没有被访问过
                tarjan(j);//访问j点
                low[a]=min(low[a],low[j]);//用j点能到达的最小值来更新这个点能到达的最小值
            }
            else{//如果j点被访问过
                if(instack[j]==1){//假如j点在栈中，即它仍属于这个环而不是已经被划分到另一个环中
                    low[a]=min(low[a],low[j]);//用j点能到达的最小值来更新这个点能到达的最小值
                }
            }
        }
        if(dfn[a]==low[a]){//当这个点能到达的最小值在更新后仍然等于自己
            int j=stacka[top-1];
            top--;
            instack[j]=0;
            g[gnow].push_back(j);
            inset[j]=gnow;
            while(j!=a){
                j=stacka[top-1];
                top--;
                instack[j]=0;
                g[gnow].push_back(j);
                inset[j]=gnow;
            }//从栈顶开始退栈，退到这个点为止
            gnow++;//准备好下一个环的序号
        }
    }
}
int main(){
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    scanf("%d%d",&n,&m);
    for(int i=0;i<1000000;i++){
        dfn[i]=-1;
        low[i]=-1;
    }
    int enow=0;
    int t1,t2;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&t1,&t2);
        edge[enow].x=t1;
        edge[enow].y=t2;
        enow++;
        e[t1].push_back(t2);
    }
    for(int i=1;i<=n;i++)tarjan(i);
    int flag=0,who=0,noanswer=0;
    for(int i=0;i<enow;i++){
        edge[i].x=inset[edge[i].x];
        edge[i].y=inset[edge[i].y];
        if(edge[i].x!=edge[i].y)
        in[edge[i].x]++,
        out[edge[i].y]++;
    for(int i=500000;i<gnow;i++){
        if(in[i]==0 && out[i]>=0){
            if(flag!=1){
                flag=1;
                who=i;
            }
            else{
                noanswer=1;
            }
        }
    }
    int ans=0;
    if((flag==1 && noanswer!=1 && out[who]>0)||(g[who].size()==n)){
        printf("%d",g[who].size());
    }
    else{
        printf("0");
    }
    fclose(stdin);fclose(stdout);
    return 0;
}