인기 있 는 소 (Tarjan 템 플 릿)

http://blog.csdn.net/qq_34374664/article/details/77488976
http://blog.csdn.net/jeryjeryjery/article/details/52829142?locationNum=4&fps=1
제목: 소 한 마리 한 마리 의 소원 은 가장 인기 있 는 소 가 되 는 것 이다.지금 은 N 마리 의 소 가 있 습 니 다. M 대 정수 (A, B) 를 드 리 겠 습 니 다. 소 A 는 소 B 가 인기 가 있다 고 생각 합 니 다.이런 관 계 는 전달 적 인 것 으로 A 가 B 가 인기 가 있다 고 생각 하고 B 가 C 가 인기 가 있다 고 생각한다 면 우 A 도 우 C 가 인기 가 있다 고 생각한다.당신 의 임 무 는 소 몇 마리 가 모든 소 에 게 인기 가 있다 고 생각 하 는 지 구 하 는 것 입 니 다.
입력: 첫 줄 두 개 N, M.다음 M 줄, 줄 당 두 개의 숫자 A, B 는 A 가 B 가 인기 가 있다 고 생각 한 다 는 뜻 이다.
출력: 하나의 정 수 를 출력 합 니 다. 즉, 몇 마리 의 소 가 모든 소 에 게 인기 가 있다 고 생각 합 니까?이러한 조건 을 만족 시 키 지 않 으 면 '0' 을 출력 합 니 다.
EG: in: 3 3 1 2 2 1 2 3
out: 1
코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

struct hehe
{
    int u,v,next;
}bian[100050];

int n,m;
int low[500050],dfn[500050];
int num[500050],head[500050],chudu[500050],belong[500050];
int zhan[500050];
int cnt=0,tj=0,top=0,tot=0;
bool fangwen[500050];

inline void jianbian(int U,int V)
{
    tj++;
    bian[tj].u=U;
    bian[tj].v=V;
    bian[tj].next=head[U];
    head[U]=tj;
}

inline void soudian(int u)
{
    low[u]=dfn[u]=++cnt;
    zhan[++top]=u;
    fangwen[u]=true;

    for(int p=head[u];p!=-1;p=bian[p].next)
    {
        int v=bian[p].v;

        if(!dfn[v])
        {
            soudian(v);
            low[u]=min(low[u],low[v]);
        }
        else
        if(fangwen[v])
            low[u]=min(low[u],dfn[v]);
    }

    if(low[u]==dfn[u])
    {
        ++tot;
        int v=-1;
        while(u!=v)
        {
            v=zhan[top--];
            belong[v]=tot;
            num[tot]++;
            fangwen[v]=false;
        }
    }
}

int main()
{
    memset(head,-1,sizeof(head));

    cin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin>>u>>v;
        jianbian(u,v);
    }

    for(int i=1;i<=n;++i)
        if(!dfn[i])
            soudian(i);

    for(int i=1;i<=m;++i)
        if(belong[bian[i].u]!=belong[bian[i].v])
            chudu[belong[bian[i].u]]++;

    int res=0,ans;
    for(int i=1;i<=tot;++i)
        if(chudu[i]==0)
        {
            res++;
            ans=i;
        }

    if(res==1) cout<else       cout<<0;

    return 0;
}