Popular Cows 【tarjan求缩点】

题目链接：POJ-1286

## **题目描述**：

题意就是说 给定n头牛，m种关系，然后给定关系a, b代表着a认为b最帅，然后这种关系有着传递性，就是 a认为 b最帅，b认为c最帅，则a也认为c最帅。 然后要求出被其他所有牛都认为是最帅的奶牛有多少头；

思路

用例：

可以明确看出，只有第3只牛满足题意；所以输出1；

那么我们如何解这道题呢？我们可以用tarjan算法将图中的强联通分量缩为一个点，即缩点；然后找出出度为0的缩点，该缩点的大小就是我们所求的答案；
如何理解呢？

随手画的一个图，我们可以看出，3， 4， 5都为最帅的牛；所以答案为3; 我们缩点之后就变为了

这样的样子，可以看出只有节点3的出度为0，所以直接输出节点3的大小即可;

然后我们统计出度为0的缩点个数，为1的话，我们直接输出当前缩点的环大小；
否则输出0即可；

AC代码

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

#define MAX_N 10010

stack<int> S;
vector<int> g[MAX_N], scc[MAX_N];
int in_stack[MAX_N], dfn[MAX_N], low[MAX_N], idx = 1, ans_scc = 0, belong[MAX_N], out[MAX_N];

void tarjan(int u)
{
    low[u] = dfn[u] = idx++;
    S.push(u);
    in_stack[u] = 1;
    for(int i = 0; i<g[u].size(); i++)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(in_stack[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        ans_scc++;
        do
        {
            int k = S.top();
            belong[k] = ans_scc;
            in_stack[k] = false;
            S.pop();
            scc[ans_scc].push_back(k);
            if(u == k)
                break;
        }
        while(!S.empty());
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i<m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
    }
    memset(dfn, 0, sizeof(dfn));
    for(int i = 1; i<=n; i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(int i = 1; i<=n; i++)
    {
        int sz = g[i].size();
        for(int j = 0; j < sz; j++)
        {
            int v = g[i][j];
            if(belong[v] != belong[i])
            {
                out[belong[i]]++;
            }
        }
    }
    int tmp = 0,  ans;
    for(int i = 1; i<=ans_scc; i++)
    {
        if(out[i] == 0)
        {
            tmp++;
            ans = scc[i].size();
        }
    }
    if(tmp != 1)
    {
        cout << 0;
    }
    else
        cout << ans;
    return 0;
}