首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >确定比赛名次(拓扑排序) - HDU 1285

确定比赛名次(拓扑排序) - HDU 1285

作者头像
ACM算法日常
发布2018-08-07 18:27:46
1.1K0
发布2018-08-07 18:27:46
举报
文章被收录于专栏:ACM算法日常ACM算法日常

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这题之后,对拓扑排序有一个比较深的印象。

拓扑排序并不是常规的排序,在图G结构中,如果G是有向无环图(简单可以理解是向量+不能从出发地回到出发地),如果G中包含边(u,v),则节点u在拓扑排序中处于节点v的前面。

可以将图的拓扑排序看作是将图的所有节点在一条水平线上排开,节点之间的有向边都是从左指向右。

也就是说,拓扑排序的输入是一个图结构,输出是一个序列,这个序列的顺序依赖图G中每个节点的先后关系进行排序。

拓扑排序在生活中的例子,就如穿衣服,穿衣服有先后,我们就可以对穿衣服作一个拓扑排序,输出类似于:内衣 -> 裤子 -> 袜子 -> 鞋子 -> ...。

拓扑排序在计算机中的应用比如Makefile文件的依赖关系,再如Linux系统的包依赖管理如apt、yum等。

也就是说,对于这种存在先后依赖关系的逻辑,都可以用拓扑排序来做。

进入正题:

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

4 3

1 2

2 3

4 3

Sample Output

1 2 4 3

解题思路:

本题中典型的先后依赖,因此用拓扑排序的方法来解。

源代码:G++ 30ms

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int main()
{
    //队伍数量,输赢数量
    int team_count, order_count;
    //图
    vector<int> Graph[1000];
    //输的次数(被依赖的次数)
    int lose[1000];
    //优先级队列
    priority_queue <int, vector<int>, greater<int> > prior_q;

    int i, j, k;

    while (~scanf("%d %d", &team_count, &order_count)) {
        //清空图
        for (i = 1; i <= team_count; ++i) {
            Graph[i].clear();
        }
        //清空
        memset(lose, 0, sizeof(lose));
        //输入输赢情况
        for (i = 1; i <= order_count; ++i) {
            scanf("%d %d", &j, &k);
            //
            Graph[j].push_back(k);
            //k队输的数量(也是被依赖的数量,或者G图中箭头所指的数量)
            lose[k]++;
        }
        //找出没有输记录的队伍(不需要被依赖)
        for (i = 1; i <= team_count; ++i) {
            if (lose[i] == 0) {
                prior_q.push(i);
            }
        }

        int cnt = 0;
        //
        while (!prior_q.empty()) {
            //prior_q里面都是0,所以直接pop
            int x = prior_q.top();
            prior_q.pop();
            //处理完了标记,-1表示已处理
            lose[x] = -1;
            printf("%d", x);
            cnt++;
            //如果已经输出到最后一个了,输出换行
            if (cnt == team_count) {
                printf("\n");
            } else {
                printf(" ");
            }
            
            for (i = 0; i < Graph[x].size(); ++i) {
                //依赖减少1
                lose[Graph[x][i]]--;
                //如果没有依赖了,则放到prior_q里
                if (!lose[Graph[x][i]]) {
                    prior_q.push(Graph[x][i]);
                }
            }
        }
    }
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-02-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档