【题解】LuoGu2341：[HAOI2006]受欢迎的牛

原题传送门
先用tarjan缩点形成一个DAG
然后两种做法
一种缩好点后统计每个点的入度，若入度为总数-1，就是受欢迎的牛，然后我就wa掉了，因为新边可能重复
所以换个角度，如果某个新点出度为0，那么是受欢迎的牛，但是若出度为0的点有多个，答案就是0（yy一下）

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Edge{
    int to, next;
}edge[maxn];
int num, head[maxn], Index, dfn[maxn], low[maxn], vis[maxn], top, sta[maxn];
int tot, color[maxn], sum[maxn], x[maxn], y[maxn], n, m, out[maxn];

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){ y, head[x] }; head[x] = num; }

void tarjan(int u){
    dfn[u] = low[u] = ++Index;
    vis[u] = 1, sta[++top] = u;
    for (int i = head[u]; i; i = edge[i].next){
        int v = edge[i].to;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else
        if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]){
        ++tot;
        while (sta[top + 1] != u)
            color[sta[top]] = tot, vis[sta[top--]] = 0, ++sum[tot];
    }
}

int main(){
    n = read(), m = read();
    for (int i = 1; i <= m; ++i){
        x[i] = read(), y[i] = read();
        addedge(x[i], y[i]);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
    num = 0;
    memset(head, 0, sizeof(head));
    for (int i = 1; i <= m; ++i)	
        if (color[x[i]] != color[y[i]])
            addedge(color[x[i]], color[y[i]]), ++out[color[x[i]]];
    int ans = 0, cnt = 0;
    for (int i = 1; i <= tot; ++i)
        if (!out[i]) ans += sum[i], ++cnt;
    printf("%d\n", cnt == 1 ? ans : 0);
    return 0;
}