Description

原题来自：USACO 2003 Fall

每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

Input

第一行两个数 N，M；

接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。

Output

输出被除自己之外的所有牛认为是受欢迎的牛的数量。

Sample Input 1

3 3
1 2
2 1
2 3

Sample Output 1

1

Hint

样例说明

只有第三头牛被除自己之外的所有牛认为是受欢迎的。

数据范围：

对于全部数据，1≤N≤10,000；1≤M≤50,000

题目大意：

找出被除自己以外所有牛欢迎的牛，典型的强连通分量，找出所有的强连通分量，然后进行压点，如果想满足题目要求，就必须让所有点中出度为0的点有且仅有一个。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+5;
int low[maxn],instack[maxn],dfn[maxn];
int Stack[maxn],in[maxn],t[maxn],tt[maxn];
int tot,num,cnt;
int n,m;

struct node
{
    int v;
    node(int vv):v(vv){}
};
vector<node>e[maxn];

void add_edge(int u , int v)
{
    e[u].push_back(node(v));
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++tot;
    Stack[++num] = u;
    instack[u] = 1;
    for(int i = 0 ; i < e[u].size() ; i++)
    {
        int v = e[u][i].v;
        if(dfn[v] == 0)
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(instack[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        while(u != Stack[num])
        {
            t[Stack[num]] = cnt;
            tt[cnt]++;
            instack[Stack[num]] = 0;
            num--;
        }
        t[Stack[num]] = cnt;
        tt[cnt]++;
        instack[Stack[num]] = 0;
        num--;
        cnt++;
    }
}


int main()
{
    cin >> n >> m;
    for(int i = 0 ; i < m ; i++)
    {
        int u,v;
        cin >> u >> v;
        add_edge(u,v);    
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    int sum = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < e[i].size() ; j++)
        {
            int v = e[i][j].v;
            if(t[i] != t[v])
                in[t[i]]++;
        }
    }
    int flag = 0;
    for(int i = 0 ; i < cnt ; i++)
    {
        if(!in[i])
        {
            flag++;
            sum = tt[i];
        }
    }
    if(flag == 1)
        cout << sum << endl;
    else
        cout << "0" << endl;
    return 0;
}