Problem Description
有N個比賽隊（1<=N<=500），編號依次為1，2，3，。。。。，N進行比賽，比賽結(jié)束后，裁判委員會要將所有參賽隊伍從前往后依次排名，但現(xiàn)在裁判委員會不能直接獲得每個隊的比賽成績，只知道每場比賽的結(jié)果，即P1贏P2，用P1，P2表示，排名時P1在P2之前。現(xiàn)在請你編程序確定排名。

Input
輸入有若干組，每組中的第一行為二個數(shù)N（1<=N<=500），M；其中N表示隊伍的個數(shù)，M表示接著有M行的輸入數(shù)據(jù)。接下來的M行數(shù)據(jù)中，每行也有兩個整數(shù)P1，P2表示即P1隊贏了P2隊。

Output
給出一個符合要求的排名。輸出時隊伍號之間有空格，最后一名后面沒有空格。

其他說明：符合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前；輸入數(shù)據(jù)保證是正確的，即輸入數(shù)據(jù)確保一定能有一個符合要求的排名。

Sample Input
4 3
1 2
2 3
4 3

Sample Output
1 2 4 3

裸的字典序最小拓撲排序

#include <cstdio> #include <cstring> #define MAXN 517 int G[MAXN][MAXN]; //路徑 int in_degree[MAXN]; //入度 int ans[MAXN]; int n, m, x, y; int i, j;void toposort() {for (i = 1; i <= n; i++) //從最小的開始尋找，{ //這樣保證了有多個答案時序號小的先輸出int k = 1;while (in_degree[k] != 0) //尋找入度為零的點k++;ans[i] = k;in_degree[k] = -1;//更新為-1，后邊檢測不受影響，相當(dāng)于刪除節(jié)點for (int j = 1; j <= n; j++){if (G[k][j])in_degree[j]--; //相關(guān)聯(lián)的入度減1}} }void init() {memset(in_degree, 0, sizeof(in_degree));memset(ans, 0, sizeof(ans));memset(G, 0, sizeof(G)); }int main() {while (~scanf("%d%d", &n, &m)){init();for (i = 0; i < m; i++){scanf("%d%d", &x, &y);if(G[x][y]==0) in_degree[y]++;G[x][y] = 1;}toposort();for (i = 1; i < n; i++)printf("%d ", ans[i]);printf("%d\n", ans[n]);}return 0; }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。