閱讀976 返回首頁    go 阿裏雲 go 技術社區[雲棲]

九度題目1449：確定比賽名次

題目1449：確定比賽名次
時間限製：1 秒內存限製：128 兆特殊判題：否提交：669解決：293
題目描述：
有N個比賽隊（1<=N<=500），編號依次為1，2，3，。。。。，N進行比賽，比賽結束後，裁判委員會要將所有參賽隊伍從前往後依次排名，但現在裁判委員會不能直接獲得每個隊的比賽成績，隻知道每場比賽的結果，即P1贏P2，用P1，P2表示，排名時P1在P2之前。現在請你編程序確定排名。
輸入：
輸入有若幹組，每組中的第一行為二個數N（1<=N<=500），M；其中N表示隊伍的個數，M表示接著有M行的輸入數據。接下來的M行數據中，每行也有兩個整數P1，P2表示即P1隊贏了P2隊。
輸出：
給出一個符合要求的排名。輸出時隊伍號之間有空格，最後一名後麵沒有空格。
其他說明：符合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前；輸入數據保證是正確的，即輸入數據確保一定能有一個符合要求的排名。
樣例輸入：
4 3
1 2
2 3
4 3
樣例輸出：
1 2 4 3








//拓撲排序
/*拓撲排序方法如下:
(1)從有向圖中選擇一個沒有前驅(即入度為0)的頂點並且輸出它.
(2)從網中刪去該頂點,並且刪去從該頂點發出的全部有向邊.

(3)重複上述兩步,直到剩餘的網中不再存在沒有前趨的頂點為止.*/

AC代碼：

#include<stdio.h>
#include<string.h>
int degree[510],bin[510],map[510][510];
void ToPu(int n)
{
   int i,j,p;
   for(i=1;i<=n;i++)
   {
      p=-1;//用來記錄入度為0的結點 
      for(j=1;j<=n;j++)
      {
         if(degree[j]==0)//如果入度為0 
         {
           degree[j]--;//讓他為負數
           bin[i]=p=j;
           break;//找到那個入度為0的結點，說明他是本組查找的元老 
         } 
      }
      for(j=1;j<=n;j++)
      {
        if(map[p][j]==1)//去掉p鏈接的所有路 
        {
           map[p][j]=0;
           degree[j]--;//j的入度減去1 
        } 
      }
   }    
}
int main()
{
    int i,j,n,m,x,y;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
       memset(degree,0,sizeof(degree));
       memset(bin,0,sizeof(bin));
       memset(map,0,sizeof(map));
       for(i=0;i<m;i++)    
       {
           scanf("%d %d",&x,&y);
           if(map[x][y]==0)  
           {
              map[x][y]=1;
              degree[y]++;//y點的入度加一 
           }              
       } 
       ToPu(n);   
       printf("%d",bin[1]);
       for(i=2;i<=n;i++)
       printf(" %d",bin[i]);
       puts("");     
    }
    return 0;
}

最後更新：2017-04-03 08:26:11

  上一篇：go Vmware Tools怎麼安裝
  下一篇：go 九度題目1087：約數的個數