# [Luogu] 受欢迎的牛

https://www.luogu.org/problemnew/show/P2341

Tarjan 缩点 + 判断出度

```#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;

#define yxy getchar()

int Tarjan_tim, now = 1, n, m, topp, bel;
int Stack[N], head[N], dfn[N], low[N], belong[N], Cnt[N], Out[N];
struct Node {int u, v, nxt;} G[M];
bool vis[N];

int x = 0; char c = yxy;
while(c < ‘0‘ || c > ‘9‘) c = yxy;
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = yxy;
return x;
}

inline void add(int u, int v){
G[now].u = u; G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;
}

void Tarjan(int u){
dfn[u] = low[u] = ++ Tarjan_tim;
vis[u] = 1;
Stack[++ topp] = u;
for(int i = head[u]; ~ i; i = G[i].nxt){
int v = G[i].v;
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], low[v]);
}
if(dfn[u] == low[u]){
vis[u] = 0; belong[u] = ++ bel;
while(Stack[topp] != u){
vis[Stack[topp]] = 0;
belong[Stack[topp]] = bel;
topp --;
}
topp --;
}
}

int main()
{
for(int i = 1; i <= n; i ++) head[i] = -1;
for(int i = 1; i <= m; i ++) {
}
for(int i = 1; i <= n; i ++) if(!dfn[i]) Tarjan(i);
for(int u = 1; u <= n; u ++){
for(int i = head[u]; ~ i; i = G[i].nxt){
int v = G[i].v;
if(belong[u] != belong[v]) Out[belong[u]] ++;
}
Cnt[belong[u]] ++;
}
int js = 0, Ans;
for(int i = 1; i <= bel; i ++){
if(!Out[i]) {js ++; Ans = Cnt[i];}
}
if(js != 1) cout << "0";
else cout << Ans;
return 0;
}```

[Luogu] 受欢迎的牛

(0)
(0)

0条