HDu 1285トポロジーソート


試合の順位を決める
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6056    Accepted Submission(s): 2275
Problem Description
Nチーム(1<=N<=500)があり、番号は1、2、3、...Nは試合を行い、試合が終わった後、審判委員会はすべての参加チームを行った後から順番に順位をつけなければならないが、現在、審判委員会は直接各チームの試合成績を得ることができず、各試合の結果、すなわちP 1がP 2に勝ったことしか知らず、P 1,P 2で表され、順位はP 1がP 2の前にある.今、プログラムを作ってランキングを確定してください.
 
Input
入力にはいくつかのグループがあり、各グループの第1の動作の2つの数N(1<=N<=500)、M;ここで、Nは行列の個数を表し、MはM行に続く入力データを表す.次のM行データでは、行ごとに2つの整数P 1があり、P 2はP 1チームがP 2チームに勝ったことを示す.
 
Output
要件に合致するランキングを与えます.出力時にキュー番号の間にスペースがあり、最後の名前の後ろにスペースがありません.
その他の説明:条件に合致する順位は唯一ではない可能性があります.この場合、出力時の番号の小さいチームが上位にあることが要求されます.入力データは正しいことを保証します.すなわち、入力データは必ず要求に合致するランキングを確保します.
 
Sample Input

   
   
   
   
4 3 1 2 2 3 4 3

 
Sample Output

   
   
   
   
1 2 4 3

最初のいくつかの拡張ソート、多くの脆弱性の神馬、先にコードを貼ります
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//  INT_MAX   
#define MAX 1050
#define INF 0x7FFFFFFF
# define eps 1e-5
using namespace std;
int head[505][505],list[505],vis[505];//head     list   vis    ;
int deg[505],n,m;//deg    
int topsort()
{
    queue<int> q;
    int i,temp=0;
    for(i=1; i<=n; i++)//        0  ,  
    {
        if(deg[i] == 0 )
        {
            q.push(i);
            vis[i] = 1;
            list[temp++] = i;
            break;
        }
    }
    while( !q.empty())//     
    {
        int t = q.front();
        q.pop();
        for(i=1; i<=n; i++)//          
        {
            if(head[t][i])
                deg[i]--;
        }
        for(i=1; i<=n; i++)//        ,  
        {
            if(! vis[i] && deg[i] == 0)
            {
                q.push(i);
                list[temp++] = i;
                vis[i] = 1;
                break;
            }
        }
    }
    return temp;
}
int main()
{
    int i,j,a,b;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        memset(list,0,sizeof(list));
        memset(head,0,sizeof(head));
        memset(deg,0,sizeof(deg));
        memset(vis,0,sizeof(vis));
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            if(head[a][b] == 0)// discuss,      ....  wa 
            {
                head[a][b] = 1;//     
                deg[b] ++;//    ++
            }
        }
        int ans=topsort();
        for(i=0; i<ans-1; i++)//    
            printf("%d ",list[i]);
        printf("%d
",list[ans-1]); } return 0; }