[Bzoj1051][HAOI2006]受欢迎的牛(tarjan)

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1051

由题意可知，被所有牛仰慕的牛之间也互相仰慕，则最后的答案一定是唯一的强连通分量，如图：

且这个强连通分量出度为0。

所以用tarjan缩环，然后在判断出度为0的是否有且仅有一个点。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 struct node {

     int e, next;

 }edge[];

 int head[maxn * ], len;

 void add(int s, int e) {

     edge[++len].e = e;

     edge[len].next = head[s];

     head[s] = len;

 }

 int color[maxn], dfn[maxn], low[maxn], vis[maxn];

 int out[maxn];

 int num[maxn];

 int dfsnum, ansnum, top;

 stack<int>q;

 void tarjan(int x) {

     dfn[x] = low[x] = ++dfsnum;

     vis[x] = ;

     q.push(x);

     for (int i = head[x]; i; i = edge[i].next) {

         int y = edge[i].e;

         if (!dfn[y]) {

             tarjan(y);

             low[x] = min(low[x], low[y]);

         }

         else if (vis[y])

             low[x] = min(low[x], dfn[y]);

     }

     if (low[x] == dfn[x]) {

         ansnum++;

         int y;

         do {

             y = q.top();

             q.pop();

             color[y] = ansnum;

             num[ansnum]++;

             vis[y] = ;

         } while (x != y);

     }

 }

 int main() {

     int n, m, x, y;

     scanf("%d%d", &n, &m);

     for (int i = ; i <= m; i++) {

         scanf("%d%d", &x, &y);

         add(x, y);

     }

     for (int i = ; i <= n; i++)

         if (!dfn[i])

             tarjan(i);

     for (int x = ; x <= n; x++) {

         for (int i = head[x]; i; i = edge[i].next) {

             int y = edge[i].e;

             if (color[x] != color[y])

                 out[color[x]]++;

         }

     }

     int ans = , f = ;

     for (int i = ; i <= ansnum; i++)

         if (out[i] == )ans = num[i], f++;

     if (f == )

         printf("%d\n", ans);

     else

         printf("0\n");

 }