確定比賽名次 Problem Description 有N個比賽隊（1<=N<=500），編號依次為1，2，3，。。。。，N進行比賽，比賽結束后，裁判委員會要將所有參賽隊伍從前往后依次排名，但現在裁判委員會不能直接獲得每個隊的比賽成績，只知道每場比賽的結果，即P1贏P2，用P1，P2表示，排名時P1在P2之前?，F在請你編程序確定排名。
Input 輸入有若干組，每組中的第一行為二個數N（1<=N<=500），M；其中N表示隊伍的個數，M表示接著有M行的輸入數據。接下來的M行數據中，每行也有兩個整數P1，P2表示即P1隊贏了P2隊。
Output 給出一個符合要求的排名。輸出時隊伍號之間有空格，最后一名后面沒有空格。 其他說明：符合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前；輸入數據保證是正確的，即輸入數據確保一定能有一個符合要求. Sample Input 4 3 1 2 2 3 4 3 Sample Output 1 2 4 3 1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=1000; 8 int b[MAXN][MAXN]; //鄰接矩陣 9 int n,m,sum; 10 int topsort() 11 { 12 bool Visit[MAXN]; 13 for(int i=1;i<=n;i++) 14 Visit[i]=false; //避免重復訪問 15 for(int o=1;o<=n;o++) //遍歷n次 16 { 17 for(int j=1;j<=n;j++) //遍歷n列 18 { 19 sum=0; //入度初始化為零 20 for(int i=1;i<=n;i++) 21 { 22 sum+=b[i][j]; //計算節點的入度 23 } 24 if(!Visit[j] && sum==0) //如果該節點沒有訪問過且入讀為零 25 { 26 printf("%d ",j); //輸出節點 27 Visit[j]=true; //標記該節點已訪問過 28 for(int k=1;k<=n;k++) 29 b[j][k]=0; //與j節點相鄰的所有節點入度清零 30 } 31 } 32 } 33 } 34 int main() 35 { 36 int win,fail; 37 cin>>n>>m; 38 memset(b,0,sizeof(b)); 39 for(int i=1;i<=m;i++) 40 { 41 cin>>win>>fail; 42 b[win][fail]=1; //放入鄰接矩陣 43 } 44 topsort(); //執行拓撲排序 45 return 0; 46 }

?

轉載于:https://www.cnblogs.com/Victor-ZhaoYiWei/p/7137847.html

總結

以上是生活随笔為你收集整理的拓扑排序 确定比赛名次的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。