Description

　　挑竹签——小时候的游戏

　　夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。

　　挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。

　　身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？

　　为了简化问题，我们假设当且仅当挑最上层的竹签不会动到其他竹签。

Input

　　输入文件mikado.in。

　　第一行输入两个整数n,m, 表示竹签的根数和竹签之间相压关系数。

　　第二行到m+1 行每行两个整数u,v，表示第u 根竹签压住了第v 根竹签。

Output

　　输出文件mikado.out。

　　一共一行，一个整数sum，表示最多能拿走sum 根竹签。

Sample Input

　　6 6 　　1 2 　　2 3 　　3 1 　　4 3 　　4 5 　　6 5

Sample Output

　　3 　　样例解释： 　　一共有6 根竹签，其中1 压住2，2 压住3，3 压住1，4 压住3 和5，6 压住5。最优方案中，我们可以依次挑走4、6、5 三根竹签。而剩下的三根相互压住，都无法挑走。所以最多能挑走3 根竹签。

Data Constraint

　　对于20% 的数据，有1<= n,m<= 20。

　　对于40% 的数据，有1 <= n,m <= 1 000。

　　对于100% 的数据，有1 <= n,m <= 1 000 000。

Summary

　　拓扑排序，先挑走入度为0的竹签i，再把竹签i压住的竹签入度-1，如果为0就放入队列中，直到队列清空。

1 #include 
          
            2 using namespace std; 3 struct arr  4 {  5 int x,y,next; 6 }; 7 arr edge[1500000]; 8 int ls[1500000],t[1500000],d[1500000],l,r; 9 int ss(int x)10 {11     int i=ls[x];12     while (i!=0) 13     {14         d[edge[i].y]--;15         if (d[edge[i].y]==0)16         {17             r++;18             t[r]=edge[i].y;19         }20         i=edge[i].next;21     }22 }23 int main()24 {25     int n,m;26     scanf("%d%d",&n,&m);27     for (int i=1;i<=m;i++)28     {29         scanf("%d%d",&edge[i].x,&edge[i].y);30         edge[i].next=ls[edge[i].x];31         ls[edge[i].x]=i;32         d[edge[i].y]++;33     }34     l=1;r=0;35     for (int i=1;i<=n;i++)36         if (d[i]==0)37             t[++r]=i;38     while (l<=r)39     {40         ss(t[l]);41         l++;42     }43     printf("%d\n",r);44 }