1513：【例 1】受欢迎的牛

【题目描述】

原题来自：USACO 2003 Fall

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

第一行两个数 N,M；

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

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

3 3
1 2
2 1
2 3

【输出样例】

【提示】

样例说明

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

数据范围：

对于全部数据，1≤N≤104,1≤M≤5×104
。

Tarjan 算法求强联通分量后缩点。出度为 0 的点必然是被所有的牛欢迎。统计入度为 0 的点，如果入度为 0 的点不止一个，则说明原图是不联通的。
答案就是缩点后入度为0点包含的牛的个数

证明：如果存在一头牛 U 受所有牛欢迎且存在牛 V （U ，V 不在同一分量中）使得边 U -> V 存在，则显然有 U -> V 与 V -> U （U 欢迎 V，V 欢迎 U），U， V 之间存在环，说明U ，V 在同一分量中，矛盾。

如果存在不止一个出度为0的分量构成集合{U1， U2， u3 ..., Un}，则{U1， U2， u3 ..., Un}中任意两点两两不连通，没有牛受所有牛欢迎。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx;
int dfn[N],low[N], timestamp;
int stk[N], top;
bool st[N];

int id[N],siz[N],scc_cnt;

int n, m;
int dout[N];

void tarjan(int u)//tarjan算法
{
    dfn[u] = low[u] = ++timestamp;
    stk[ ++ top] = u;
    st[u] = 1;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (st[j]) low[u] = min(low[u], dfn[j]);
    }
    if(dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top --];
            st[y] = 0;
            id[y] = scc_cnt;
            siz[scc_cnt]++;
        }while(y != u);
    }
}

void add(int a,int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

int main()
{
    scanf("%d %d",&n,&m);
    memset(h, -1, sizeof(h));
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d %d",&a,&b);
        add(a, b);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++)
    {
        for(int j = h[i] ; ~j ;j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if(a != b) dout[a]++;//统计出度
        }
    }
    int zeros = 0, sum = 0;
    for(int i = 1; i <= scc_cnt; i++)
    {
        if(!dout[i])
        {
            zeros++;//统计出度为0的点的个数
            sum += siz[i];
        }
        if(zeros >= 2)//不止一个
        {
            sum = 0;
            break;
        }
    }
    printf("%d",sum);
    return 0;
}

1513：【 例 1】受欢迎的牛

推荐阅读

1513：【例 1】受欢迎的牛