4269. 【NOIP2015模拟10.27】挑竹签 
(File IO): input:mikado.in output:mikado.out

Goto ProblemSet

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <string>

 #define N 1000007

 using namespace std;

 struct edge

 {

     int to, next;

 }e[N * ];

 int rd[N], n, m, ls[N], tot, list[N];

 bool v[N];

 int read()

 {

     int s = ;

     char c = getchar();

     while (c < '' || c > '')    c = getchar();

     while (c >= ''    && c <= '')    s = s *  + c - '', c = getchar();

     return s;

 }

 int main()

 {

     freopen("mikado.in", "r", stdin);

     freopen("mikado.out", "w", stdout);

     n = read(), m = read();

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

     {

         int x, y;

         x = read(), y = read();

         rd[y]++;

         e[++tot].to = y;

         e[tot].next = ls[x];

         ls[x] = tot;

     }

     int head = , tail = ;

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

         if (rd[i] == )    list[++tail] = i, v[i] = ;

     while (head <= tail)

     {

         head++;

         for (int i = ls[list[head]]; i; i = e[i].next)

         {

             rd[e[i].to]--;

             if (rd[e[i].to] ==  && !v[e[i].to])

             {

                 v[e[i].to] = ;

                 list[++tail] = e[i].to;

             }

         }

     }

     printf("%d", tail);

 }