[BZOJ] 1051: [HAOI 2006] 인 기 있 는 소.

[HAOI 2006] 잘 나 가 는 소.
Description
모든 소의 소원 은 가장 환 영 받 는 소 가 되 는 것 이다.지금 은 N 마리 의 소 가 있 습 니 다. M 대 정수 (A, B) 를 드 리 겠 습 니 다. 소 A 는 소 B 가 인기 가 있다 고 생각 합 니 다.이런 관 계 는 전달 적 인 것 으로 A 가 B 가 인기 가 있다 고 생각 하고 B 가 C 가 인기 가 있다 고 생각한다 면 우 A 도 우 C 가 인기 가 있다 고 생각한다.당신 의 임 무 는 소 몇 마리 가 모든 소 에 게 인기 가 있다 고 생각 하 는 지 구 하 는 것 입 니 다.
Input
첫 줄 두 개 N, M.다음 M 줄, 줄 당 두 개의 숫자 A, B 는 A 가 B 가 인기 가 있다 고 생각 한 다 는 뜻 이다.
Output
한 마리 의 소 가 모든 소 에 게 인기 가 있다 고 여 겨 지 는 지 세 어 보 자.
Sample Input
3 3 1 2 2 1 2 3
Sample Output
1
HINT
100% 데이터 N < = 10000, M < = 50000
 
사고: 처음에 사용 하고 집합 을 찾 을 수 있다 고 생각 했 지만 점 에 여러 개의 부모 노드 가 있 기 때문에 소박 하고 집합 을 찾 으 면 안 된다.
이렇게 하려 면 그림 을 만들어 야 한다. Tarjan 을 사용 하여 강 한 연결 분량 을 줄 이 고 그 다음 에 축 소 를 통 해 집합 하 는 요소 (사상 일 뿐 답 이 요구 하 는 것 은 일부분 이기 때문에 도 만 보면 된다) 를 살 펴 보고 하나의 노드 만 있 는 지 확인 해 야 한다.(모든 축 점 은 링 이다. 한 점 이 다른 축 점 을 가리 키 는 방향 이 있 으 면 이 축 점 에서 모든 요 소 는 축 점 중심 점 을 가리 키 는 팬 이다) 이렇게 하면 한 점 의 출 도 만 0 이라는 것 을 설명 한다. 즉, 한 개의 노드 만 있 으 면 된다. 그러면 이 노드 가 대표 하 는 축 점 중 점 수 는 answer 이다.
 
ps: Tarjan 이후 각 변 을 옮 겨 다 닌 다 고 생각 하기 시 작 했 습 니 다.; 그러나 이런 사상 은 잘못된 것 이다. 분석 할 때 단독 적 인 두 개의 축 점 간 의 관 계 를 보 았 기 때문이다. set 배 중 을 사용 하 더 라 도 두 개의 축 점 사이 에 배 중 을 실현 할 수 있 기 때문이다. 그러면 세 개의 축 점 으로 확장 하면 중복 계산 이 나타 날 수 있다.

/********************************************************
    Time:88 ms
    Memory:2888 kb
****************************************************************/

#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
const int MAXN = 50050;
int head[MAXN],tot;
struct edge{
    int to,w,Next;
}e[MAXN];
void ins(int a,int b,int w = 0)
{
    e[++tot].Next = head[a];
    e[tot].to = b;
    e[tot].w = w;
    head[a] = tot;
}
const int N = 10020;
int pre[N],dfs_clock,low[N];
int belong[N],scc,num[N];
stack<int> S;
bool stk[N];
void Tarjan(int u)
{
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    stk[u] = true;
    int v;// u         ；
    for(int i = head[u];i;i = e[i].Next){
        v = e[i].to;
        if(pre[v] == 0){
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }else if(stk[v]){
            low[u] = min(low[u],pre[v]);
        }
    }
    if(pre[u] == low[u]){//         
        ++scc;
        do{
            v = S.top();
            S.pop();stk[v] = false;
            belong[v] = scc;
            num[scc]++;
        }while(v != u);
    }
}
int id[MAXN];
int main()
{
    int T,kase = 1;
    MS0(head);tot = 0;
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    rep0(i,0,m){
        scanf("%d%d",&a,&b);
        ins(a,b);
    }
    scc = dfs_clock = 0;
    rep1(i,0,n) pre[i] = low[i] = num[i] = belong[i] = 0;
    rep1(i,1,n)if(pre[i] == 0)
        Tarjan(i);
    int ans = 0;MS0(id);
    rep1(u,1,n){
        for(int index = head[u];index;index = e[index].Next){
            int v = e[index].to;
            int bv = belong[v],bu = belong[u];
            if(bv != bu && id[bu] == 0){//***          
               id[bu]++;//      0  
            }
        }
    }
    rep1(i,1,scc)
        if(id[i] == 0){
            if(ans) return puts("0"),0;
            ans = num[i];
        }
    printf("%d
",ans);
    return 0;
}