poj 2186 Popular Cows

http://poj.org/problem?id=2186
너 에 게 n 마리 소 를 주면 그들 사이 에는 A 가 B popular 라 고 생각 하 는 관계 가 있 을 것 이다.그리고 이런 관 계 는 전달 할 수 있다.
몇 마리 의 소 가 다른 모든 소 들 에 게 인기 가 있 냐 고 물 었 습 니 다.
1.축소 점 은 하나의 연결 분량 내의 점 을 하나 로 축소 한다.
2.축 점 은 연통 분량 내 점 의 개 수 를 동시에 기록한다.
3.축 소 된 그림 이 나무 나(나무 가 아 닌)숲 으로 바 뀌 었 다.나무 라면 뿌리 가 연 결 된 분량 의 점 이 답 이다.숲 이 라면 답 은 0 이다.
    생 성 된 나무 나 숲 뿌리 방향 은 가리 키 고 있다.
4.3 의 이유 로 검색 할 때 어떤 축 점 이 뿌리 가 될 수 없 는 축 점 인지 표시 하 는 것 도 주의 하 세 요.
5.뿌리 가 움 츠 러 든 점 이 하나(나무)라면 뿌리 가 답 이다.여러 개(나무 가 아 닌 숲)는 0 이다.
Tarjan 검색 이 꼭 한 번 에 모든 점 을 다 찾 을 수 있 는 것 은 아 닙 니 다.주의 하 세 요.
코드 및 설명:

#include<iostream>

#include<cstring>

#include<stack>

#include<cstdio>

#include<queue>



using namespace std;



const int N=10005;

struct node

{

    struct tt *next;

}mem[N];

struct tt

{

    struct tt *next;

    int j;

};

int deep;

int low[N];

int dfn[N];

bool visited[N];

bool in[N];

stack<int>str;

int uppoint[N];

int th[N];//    Tarjan  

bool f[N];//                         

int sum[N];

void build(int i,int j)

{

    struct tt *t=new tt;

    t->j=j;

    t->next=mem[i].next;

    mem[i].next=t;

}

void Clearlist(int n)

{

    struct tt *t;

    for(int i=1;i<=n;++i)

    {

        while(mem[i].next!=NULL)

        {

            t=mem[i].next;

            mem[i].next=t->next;

            delete t;

        }

    }

}

void Tarjan(int pre,int x,int ith)

{

    ++deep;

    dfn[x]=low[x]=deep;

    th[x]=ith;//     Tarjan

    visited[x]=true;

    in[x]=true;

    str.push(x);

    struct tt *t=mem[x].next;

    bool think=false;

    while(t!=NULL)

    {

        if(visited[t->j]==false)

        {

            Tarjan(x,t->j,ith);

            low[x]=min(low[x],low[t->j]);

        }else if(in[t->j]==true)

        {

            low[x]=min(low[x],dfn[t->j]);

        }else if(th[t->j]<ith)//        Tarjan      x             

        {

            think=true;

        }

        t=t->next;

    }

    if(think)

    {

        f[x]=true;

    }

    if(low[x]==dfn[x])

    {

        int num=0;

        while(str.top()!=x)

        {

            uppoint[str.top()]=x;//  

            in[str.top()]=false;

            ++num;

            str.pop();

        }

        uppoint[str.top()]=x;

        in[str.top()]=false;

        ++num;

        str.pop();

        sum[x]=num;

        f[pre]=true;//              

    }

}

int main()

{

    int n,m;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        while(m--)

        {

            int i,j;

            scanf("%d %d",&i,&j);

            build(i,j);

        }

        memset(th,-1,sizeof(th));

        memset(dfn,-1,sizeof(dfn));

        memset(visited,false,sizeof(visited));

        memset(in,false,sizeof(in));

        memset(f,false,sizeof(in));

        memset(uppoint,-1,sizeof(uppoint));

        memset(sum,0,sizeof(sum));

        deep=0;

        for(int i=1,t=1;i<=n;++i)

        {

            if(dfn[i]==-1)//        t      

            Tarjan(0,i,t++);

        }

        for(int i=1;i<=n;++i)

        {

            if(f[i])//                     

            f[uppoint[i]]=true;

        }

        int num=0;

        int k=0;

        for(int i=0;i<=n;++i)

        {

            if(i==uppoint[i]&&!f[i])

            {

                ++num;

                k=i;

            }

        }

        if(num!=1)//         

        {

            printf("0
");

        }

        else

        {

            printf("%d
",sum[k]);

        }

        Clearlist(n);

    }

    return 0;

}