[HAOI2006]受欢迎的牛

洛谷传送门

直接tarjan求scc，然后统计出度为0的缩点，如果多余1个就输出0，只有一个就输出这个缩点里的点。

——代码

 #include <cstdio>

 #include <cstring>

 #include <stack>

 using namespace std;

 int n, m, cnt, idx, ans, k;

 int next[], to[], head[], low[], dfn[], belong[], c[];

 bool ins[];

 stack <int> s;

 inline void add(int x, int y)

 {

     to[cnt] = y;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline void tarjan(int u)

 {

     low[u] = dfn[u] = ++idx;

     s.push(u);

     ins[u] = ;

     int i, v;

     for(i = head[u]; i != -; i = next[i])

     {

         v = to[i];

         if(!dfn[v])

         {

             tarjan(v);

             low[u] = min(low[u], low[v]);

         }

         else if(ins[v]) low[u] = min(low[u], dfn[v]);

     }

     if(low[u] == dfn[u])

     {

         cnt++;

         do

         {

             v = s.top();

             s.pop();

             ins[v] = ;

             belong[v] = cnt;

         }while(u != v);

     }

 }

 int main()

 {

     int i, j, x, y, u, v;

     memset(head, -, sizeof(head));

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

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

     {

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

         add(x, y);

     }

     cnt = ;

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

      if(!dfn[i])

       tarjan(i);

     for(u = ; u <= n; u++)

      for(i = head[u]; i != -; i = next[i])

      {

          v = to[i];

          if(belong[u] != belong[v]) c[belong[u]]++;

      }

     for(i = ; i <= cnt; i++)

      if(!c[i])

      {

          ans++;

          k = i;

      }

     if(ans > )    printf("");

     else

     {

         ans = ;

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

          if(belong[i] == k)

           ans++;

         printf("%d", ans);

     }

     return ;

 }