HDOJ 2647 Reward（分層拓撲排序）

超級傳送門

分層的拓撲排序，先判斷是否有環，然後再逆過來求拓撲排序,即設置兩張鄰接表，一張存前驅，一張存後繼，判斷有環沒還用前驅表，判斷至少要多少工資用後繼表。

算法寫得不好，C++能過（約500MS），但是GNU C++超時了，目前不知道原因，求大神指教。

下附代碼：

[cpp]
/*HDOJ2647
作者：陳佳潤
2013-04-26
*/ 
#include<stdio.h>  
#include<queue>  
using namespace std; 
 
typedef struct tag{ 
    int person; 
    struct tag *next; 
}Node; 
typedef struct tag1{ 
    int num; 
    Node *list; 
}List; 
 
queue<int>Q; 
 
int TopologicalOrder(List L[],int n){//拓撲排序，用來判斷是否有環  
    int i,j,a,sum=0; 
    for(i=1;i<=n;i++){//對於每一個點  
        for(j=1;j<=n;j++){//遍歷一次，找出一個適合的點  
            if(L[j].num==0){//當找到一個點沒有前驅  
                L[j].num--;//減1成為-1，這樣下次不會找到  
                sum++; 
                while(L[j].list){//它的後繼點的前驅結點數目都減1  
                    a=L[j].list->person; 
                    L[a].num--; 
                    L[j].list=L[j].list->next; 
                } 
                break; 
            } 
        } 
    } 
    return sum==n; 
} 
 
int main(){ 
    List L[10005],BL[10005];//L是後繼表，BL是前驅表  
    int n,m,i,a,b,j; 
    int k; 
    int account; 
    Node *p; 
    while(scanf("%d%d",&n,&m)!=EOF){ 
        for(i=1;i<=n;i++){//初始化  
            L[i].num=BL[i].num=0; 
            L[i].list=BL[i].list=NULL; 
        } 
        //讀入  
        for(i=1;i<=m;i++){ 
            scanf("%d%d",&a,&b); 
            p=new Node; 
            //構造前驅表  
            BL[b].num++; 
            p->person=b; 
            p->next=BL[a].list; 
            BL[a].list=p; 
            //構造後繼表  
            p=new Node; 
            L[a].num++; 
            p->person=a; 
            p->next=L[b].list; 
            L[b].list=p; 
        } 
        //判斷是否有環  
        if(TopologicalOrder(BL,n)==0){ 
            printf("-1\n"); 
            continue; 
        } 
        //逆拓撲排序計算費用  
        account=n*888; 
        k=0; 
        for(i=1;i<=n;i++){ 
            for(j=1;j<=n;j++){ 
                if(L[j].num==0){ 
                    account+=k; 
                    Q.push(j); 
                    L[j].num--; 
                } 
            } 
            k++; 
            while(!Q.empty()){ 
                int t=Q.front(); 
                Q.pop(); 
                while(L[t].list){ 
                    L[L[t].list->person].num--; 
                    L[t].list=L[t].list->next; 
                } 
            } 
             
        } 
        printf("%d\n",account); 
    } 
    return 0; 
}