HDOJ1285 確定比賽名次（拓撲排序）

標准的拓撲排序，用鄰接表來存儲

鄰接表的下標表示節點序號，鄰接表內容包括兩個部分，一個是該節點的前驅數目，一個是後繼鏈表（存放其所有後繼的鏈表）。

[cpp]
/*HDOJ1285
作者：陳佳潤
2013-04-17
*/ 
#include<iostream>  
using namespace std; 
 
typedef struct tag_node{//鄰接表的邊域節點  
    int data; 
    struct tag_node *next; 
}Node; 
 
typedef struct tag{//鄰接表  
    int num; 
    Node *node; 
}Table; 
 
int main() 
{ 
    Table table[501]; 
    int i,n,m,a,b,j; 
    Node *p; 
    //freopen("1.txt","r",stdin);  
    while(cin>>n>>m){ 
        for(i=1;i<=n;i++){//初始化  
            table[i].num=0; 
            table[i].node=NULL; 
        } 
 
        for(i=1;i<=m;i++){//構造鄰接表  
            cin>>a>>b; 
            table[b].num++; 
            p=new Node; 
            p->data=b; 
            p->next=table[a].node; 
            table[a].node=p; 
        } 
        for(i=1;i<=n;i++){//開始排序  
            for(j=1;j<=n;j++){//找到一個沒有前驅的點  
                if(table[j].num==0){//如果該點沒有前驅  
                    cout<<j; 
                    if(i!=n) cout<<" "; 
                    table[j].num=-1;//表示該點已經用過  
                    while(table[j].node!=NULL){//讓該點的所有後繼點的前驅總數-1  
                        p=table[j].node; 
                        table[j].node=table[j].node->next; 
                        table[p->data].num--; 
                    } 
                    break; 
                } 
            } 
        } 
        cout<<endl; 
 
    } 
    return 0; 
} 

/*HDOJ1285
作者：陳佳潤
2013-04-17
*/
#include<iostream>
using namespace std;

typedef struct tag_node{//鄰接表的邊域節點
 int data;
 struct tag_node *next;
}Node;

typedef struct tag{//鄰接表
 int num;
 Node *node;
}Table;

int main()
{
 Table table[501];
 int i,n,m,a,b,j;
 Node *p;
 //freopen("1.txt","r",stdin);
 while(cin>>n>>m){
  for(i=1;i<=n;i++){//初始化
   table[i].num=0;
   table[i].node=NULL;
  }

  for(i=1;i<=m;i++){//構造鄰接表
   cin>>a>>b;
   table[b].num++;
   p=new Node;
   p->data=b;
   p->next=table[a].node;
   table[a].node=p;
  }
  for(i=1;i<=n;i++){//開始排序
   for(j=1;j<=n;j++){//找到一個沒有前驅的點
    if(table[j].num==0){//如果該點沒有前驅
     cout<<j;
     if(i!=n) cout<<" ";
     table[j].num=-1;//表示該點已經用過
     while(table[j].node!=NULL){//讓該點的所有後繼點的前驅總數-1
      p=table[j].node;
      table[j].node=table[j].node->next;
      table[p->data].num--;
     }
     break;
    }
   }
  }
  cout<<endl;

 }
 return 0;
}