学步园

n(1<=n<=10000) 头牛，有 m(1<=m<=50000) 个推举关系。推举关系具有传递性，即 A 推举 B， B 推举 C，那么 A 也推举 C

问你，能够得到所有牛推举的牛有多少头？

题解：强连通分支+缩点

强连通分支为最大的连通子图，在这个子图中任意两点都是可达的。

在一个强连通分支里面，根据推举关系可知，这个强连通分支里的所有的牛都能得到其他所有的牛的推举。

我们将题目给的推举关系，看成是牛群推举图里的一条边，而且是有向的，而且可以有环。

对于环，在环中的任意点，环中其它的点都是可以到达这个点的。

而这个环就相当于一个强连通分支。

而缩点的意义在于，我们可以将推举图变成推举树，这样做的意义在于，如果这棵树的叶子节点只有一个，则这个节点在原推举图中包含了多少个点，那么其值就是我们要求的答案。如果这棵树的叶子节点大于一个，那么答案肯定为0.

因此，此题有三个步骤是关键，一，求强连通分支，二、将强连通分支缩成点。三、求叶子节点

对于一、求强连通分支的方法又tarjan算法。

对于二、我们可以在tarjan算法里增加一段缩点代码。就是在找到强连通分支的时候。

对于三、只要出度为0，就是叶子节点。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

const int  MAX_  = 10010;
typedef long long LL;

vector<int>arc[MAX_];
stack<int>s;
int dfn[MAX_], low[MAX_], cnt[MAX_], id[MAX_];
int n, m, T, ind;
bool vs[MAX_];

void tarjan(int u){
    vs[u] = 1, s.push(u);
    dfn[u] = low[u] = T++;
    int len = (int)arc[u].size();
    for(int i = 0; i < len; i++){
        int v = arc[u][i];
        if(dfn[v] == -1){
            tarjan(v);
            if(low[u] > low[v]) low[u] = low[v];
        }
        else if(vs[v] && dfn[v] < low[u]) low[u] = dfn[v];
    }
    if(dfn[u] == low[u]){
        for(int v; 1 ;){
            v = s.top();
            s.pop();vs[v] = 0;
            cnt[ind]++,id[v] = ind;
            if(u == v)break;
        }
        ind++;
    }
}


int main() {
    //int Case, n, h,v, tmp, maxh,minh, maxv,minv;
    //int x1,y1,x2,y2;
    scanf("%d%d",&n,&m);
    for(int i = 0; i <= n; i++)arc[i].clear();
    for(int i = 0, a, b; i < m; i++){
        scanf("%d%d",&a,&b);
        arc[a].push_back(b);
    }
    for(int i = 0; i <= n; i++)vs[i] = 0, dfn[i] = -1,cnt[i] = 0;
    while(!s.empty())s.pop();

    T= ind = 0;
    for(int i = 1; i <= n; i++){
        if(dfn[i] == -1)tarjan(i);
    }
    for(int i = 0; i < ind; i++)dfn[i] = 0;

    for(int i = 1; i <= n ; i++){
        int len = (int) arc[i].size(), u= id[i];
        for(int j = 0; j < len; j++){
            int v = id[arc[i][j]];
            if(u != v)dfn[u]++;
        }
    }
    int ans =0,flag =0;
    for(int i = 0; i < ind; i++){
        if(dfn[i] == 0){
            ans = cnt[i];
            flag ++;
            if(flag > 1)break;
        }
    }
    if(flag != 1)ans = 0;
    printf("%d\n",ans);

    return 0;
}