题目地址：洛谷：【P2341】[HAOI2006]受欢迎的牛 – 洛谷、BZOJ：Problem 1051. — [HAOI2006]受欢迎的牛

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入输出格式

输入格式：
第一行：两个用空格分开的整数：N和M
第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式：
第一行：单独一个整数，表示明星奶牛的数量

输入输出样例

输入样例#1：

3 3
1 2
2 1
2 3

输出样例#1：

1

说明

只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000

题解

Tarjan缩点练手。
同一SCC内的所有点都可以互达，因此不用考虑SCC内的情况，直接缩点解决。考虑出度问题，只有当一个点作为一棵叶子到根的有向树的树根时才有答案，因此有多棵树的情况是无解的。考虑出度，如果出度为0的点有两个则答案为0，如果只有一个该SCC的大小就是答案。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <utility>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

int n, m;

std::vector<int> gra[MAXN], gran[MAXN];
int deg[MAXN];

int dfn[MAXN], low[MAXN], sno[MAXN], clk, scc;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop();
            insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

std::set<std::pair<int, int> > edges;
int u, v;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint();
        gra[u].push_back(v);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v] && !edges.count(std::pair<int, int>(sno[u], sno[v]))) {
                edges.insert(std::pair<int, int>(sno[u], sno[v]));
                gran[sno[u]].push_back(sno[v]);
                deg[sno[u]]++;
            }
        }
    }
    int ansn = -1;
    for(int i = 1; i <= scc; i++) {
        if(!deg[i] && ansn != -1) {
            puts("0");
            return 0;
        }
        if(!deg[i] && ansn == -1) {
            ansn = i;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(sno[i] == ansn) {
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}