POJ---2186：Popular Cows（Tarjan缩点）

题意:

有n头奶牛，给出m对奶牛之间的仰慕关系，求有多少头奶牛能被所有奶牛仰慕

分析：

题目所求为：有多少个顶点能由其他所有顶点出发都可到达？如果图无环，那么答案就是出度为0的点；如果图存在环，环中的所有点都能互相到达，可以将环缩成一个点，如果出度为0的点大于1个，那么结果为0。

先用Tarjan算法将图中的强连通分量缩成一个点，再dfs求出每个点的出度，那么出度为0的点所在的强连通分量便是答案，出度为0的点个数大于1，则答案为0

代码：

#include <stack>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 5e4+54;
int cnt,num,n,m,x,y;
int head[MAXN],low[MAXN],dnf[MAXN],vis[MAXN],pre[MAXN],out[MAXN];
struct edge
{
    int to,nxt;
}e[MAXN];
void add(int u,int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
stack<int> s;
void tarjan(int u)
{
     low[u] = dnf[u] = ++cnt;
     s.push(u);
     vis[u] = 1;
     for(int i = head[u]; i ; i = e[i].nxt){
        int v = e[i].to;
        if(!dnf[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(vis[v]) low[u] = min(low[u],dnf[v]);
     }
     if(dnf[u] == low[u]){
        num++;
        int v;
        do{
            v = s.top();
            s.pop();
            vis[v] = 0;
            pre[v] = num;
        }while(u != v);
     }
}
void dfs(int u)
{
    vis[u] = 1;
    for(int i = head[u]; i ;i = e[i].nxt){
        int v = e[i].to;
        if(pre[u] != pre[v]) out[pre[u]]++;
        if(vis[v]) continue;
        dfs(v); 
    }
}
int main()
{
    cin>>n>>m;
    while(m--){
        cin>>x>>y;
        add(x,y);
    }
    for(int i = 1;i <= n; ++i){
        if(!dnf[i]) tarjan(i);
    }
    memset(vis,0,sizeof(vis));
    for(int i = 1;i <= n; ++i){
        if(!vis[i]) dfs(i);
    }
    int res = 0;
    for(int i = 1;i <= num; ++i){
        if(out[i] == 0){
            if(!res) res = i;
            else{
                res = 0;
                break;
            }
        }
    }
    if(!res) cout<<0;
    else{
        int ans = 0;
        for(int i = 1;i <= n; ++i) if(pre[i] == res) ans++;
        cout<<ans;
    }
    return 0;
}