hdoj1285-拓扑排序

发表于 | 分类于

题目描述

Problem Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

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

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

Sample Input

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

Sample Output

1
1 2 4 3

思路分析

本次用拓扑排序来解决。设置一个vector数组来保存有向图，另外需要设置入度数组来查找入度为0的点。同时，设置一个队列来进行遍历，另外注意，符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前，因此使用小顶堆，优先弹出的是入度为0且编号较小的号码。

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
46
47
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    vector<int> edge[501];
    //符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；
    //因此使用小顶堆，优先弹出的是入度为0且编号较小的号码。 
    priority_queue<int, vector<int>, greater<int>> q;
    int inDegree[501];
    vector<int> res;
    int n, m; //n为队伍个数，m为输入行数 
    while(cin >> n >> m){
        res.clear();
        for(int i=1; i<=n; i++){
            edge[i].clear();
            inDegree[i] = 0;
        }
        while(!q.empty()) q.pop();
        while(m--){
            int a, b;
            cin >> a >> b;
            inDegree[b] += 1;
            edge[a].push_back(b);
        }
        for(int i=1; i<=n; i++){
            if(inDegree[i] == 0) q.push(i);
        }
        while(!q.empty()){
            int newP = q.top(); // 优先队列的顶部用top()，而不是用front()
            q.pop();
            res.push_back(newP);
            for(int i=0; i<edge[newP].size(); i++){
                inDegree[edge[newP][i]]--;
                if(inDegree[edge[newP][i]] == 0){
                    q.push(edge[newP][i]);
                }
            }
        }
        for(int i=0; i<res.size(); i++){
            if(i == 0) cout << res[i];
            else cout << " " << res[i];
        }
        cout << endl;
    } 
}