cdoj 916-方先生の分身III【位相配列】

http://acm.uestc.edu.cn/#/problem/show/916
方先生の分身III
Time Limit：3000/1000 MS（Java/Others）    メモリLimit：65535/65535 KB（Java/Others）
Submit 
Status
一日の講座が終わると、方先生の分身たちが集まった。一つの先生になる前に。これらの分身は方先生の真身にあめを出すように要求します。これらの分身は方先生に少なくとも888個の砂糖を送ってもらいます。これはまだ足りないです。ある分身は他の分身の糖より多いです。先生は砂糖を最低何点に分けますか？
Input
複数のデータがあります
最初の行の2つの整数N（1≦N≦10000）、M（0≦M≦20000）は分身数と要求数を表します。
次のm行は、1行につき2つの整数x，yです。xはyよりも多くのキャンディを要求します。
Output
つの整数、方の先生は少なくともどれだけの砂糖に分けます。分糖出力−1が完了できない場合。
Sample input and output
Sample Input
Sample Output

2 1

1 2

2 2

1 2

2 1

1777

-1

 
 
 
トポロジーの順序は容易に考えられます。テーマの中で環を設計して、位相の順序付けで環の存在を判断することができます。また，トポロジーの方向に注意が必要である。
コード:

 1 #include <fstream>

 2 #include <iostream>

 3 #include <cstdio>

 4 #include <cstring>

 5 

 6 using namespace std;

 7 

 8 const int cnt=888;

 9 const int N=10005;

10 const int M=20005;

11 int n,m;

12 int u[M],v[M],head[N],la[M];

13 int du[N],cn[N];

14 bool b;

15 

16 void topology();

17 

18 int main()

19 {

20     //freopen("D:\\input.in","r",stdin);

21     //freopen("D:\\output.out","w",stdout);

22     while(~scanf("%d%d",&n,&m)){

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

24         memset(du,0,sizeof(du));

25         memset(cn,0,sizeof(cn));

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

27             scanf("%d%d",&v[i],&u[i]);

28             la[i]=head[u[i]];

29             head[u[i]]=i;

30             du[v[i]]++;

31         }

32         b=true;

33         topology();

34         if(b){

35             int ans=cnt*n;

36             for(int i=1;i<=n;i++){

37                 ans+=cn[i];

38             }

39             printf("%d
",ans);

40         }else{

41             puts("-1");

42         }

43     }

44     return 0;

45 }

46 void topology(){

47     int top=-1;

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

49         if(!du[i])  du[i]=top,top=i;

50     for(int i=0;i<n;i++){

51         if(top==-1){

52             b=false;

53             return;

54         }else{

55             int j=top;

56             top=du[top];

57             for(int k=head[j];k!=-1;k=la[k]){

58                 cn[v[k]]=max(cn[v[k]],cn[j]+1);

59                 if(!(--du[v[k]]))   du[v[k]]=top,top=v[k];

60             }

61         }

62     }

63 }