HDU-1285 确定比赛名次（拓扑序）

发表于 | 更新于: | 分类于 ， | | 阅读次数: |
字数统计: 588 | 阅读时长 ≈ 3

描述

传送门：HDU-1285 确定比赛名次

有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队。

输出描述

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

示例

输入

1
2
3
4
4 3
1 2
2 3
4 3

输出

1
1 2 4 3

题解

题目大意

中文题面

思路

比较裸的拓扑排序题。我是用邻接表写的，邻接矩阵的话注意重边即可了。还有本题符合条件的排名可能不是唯一的，此时坑点要求输出时编号小的队伍在前。其次就是输出格式的限定。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
const int MAXN = 510, INF = 0x3f3f3f3f;
using namespace std;
int n, m, u, v;
int vis[MAXN*MAXN], used[MAXN];
vector<int> E[MAXN];

int main(){
    while(~scanf("%d %d", &n, &m)){
        memset(vis, 0, sizeof(vis));
        memset(used, 0, sizeof(used));
        for(int i = 0; i <= n; i++) E[i].clear();
        for(int i = 0; i < m; i++){
            scanf("%d %d", &u, &v);
            E[u].push_back(v);
            vis[v]++;
        }
        queue<int> Q;
        for(int i = 1; i <= n; i++){
            int j = 1;
            while(used[j] || vis[j] != 0) j++;
            vis[j] = 1;
            Q.push(j);
            for(int k= 0; k < E[j].size(); k++){
                vis[E[j][k]]--;
            }
        }
        printf("%d", Q.front());
        Q.pop();
        while(!Q.empty()){
            printf(" %d", Q.front());
            Q.pop();
        }
        printf("\n");
    }
}

/*

4 3
1 2
2 3
4 3

*/