《确定比赛名次》hdu1285 优先队列+拓扑排序+链式前向星存储 杭电1285

本文主要是介绍《确定比赛名次》hdu1285 优先队列+拓扑排序+链式前向星存储 杭电1285,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

确定比赛名次

Problem Description
有N个比赛队 ( 1 < = N < = 500 ) (1<=N<=500) 1<=N<=500,编号依次为 1 , 2 , 3 , 。 。 。 。 , N 1,2,3,。。。。,N 123N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组,每组中的第一行为二个数N ( 1 < = N < = 500 ) , M (1<=N<=500),M 1<=N<=500M;其中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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 505;
int node[maxn],e[maxn],ne[maxn],tot; //邻接表 
int indeg[maxn];//入度 
int n,m;int add(int a,int b) //添加一条a -> b的边
{e[tot] = b;ne[tot] = node[a];node[a] = tot++;
}void topsort() 
{vector<int> res; //保存结果priority_queue<int,vector<int>,greater<int>> Q; //小顶(跟)堆 for(int i=1;i<=n;++i) //找到所有的入度为0的点 ,入队if(indeg[i] == 0) Q.push(i); while(Q.size()) //当队列不空{int f = Q.top(); //取队头Q.pop(); //出队res.push_back(f); //保存结果for(int i=node[f];i!=-1;i=ne[i]) //遍历当前节点的每一条出边{int j = e[i]; //获取当前节点的编号if(--indeg[j] == 0) //如果当前的节点入度为0,入队Q.push(j);}}				int len = res.size();for(int i=0;i<len;++i)printf("%d%c",res[i]," \n"[i==len-1]); //奇技淫巧输出
}int main()
{while(~scanf("%d%d",&n,&m)) //多组输入{memset(node,-1,sizeof node);memset(indeg,0,sizeof indeg); //初始化tot = 0;int a,b;while(m--){scanf("%d%d",&a,&b);add(a,b);indeg[b] ++; //b入度增加1}topsort();}return 0;
}

这篇关于《确定比赛名次》hdu1285 优先队列+拓扑排序+链式前向星存储 杭电1285的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/821389

相关文章

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

Java实现数据库图片上传与存储功能

《Java实现数据库图片上传与存储功能》在现代的Web开发中,上传图片并将其存储在数据库中是常见的需求之一,本文将介绍如何通过Java实现图片上传,存储到数据库的完整过程,希望对大家有所帮助... 目录1. 项目结构2. 数据库表设计3. 实现图片上传功能3.1 文件上传控制器3.2 图片上传服务4. 实现

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

MySQL常见的存储引擎和区别说明

《MySQL常见的存储引擎和区别说明》MySQL支持多种存储引擎,如InnoDB、MyISAM、MEMORY、Archive、CSV和Blackhole,每种引擎有其特点和适用场景,选择存储引擎时需根... 目录mysql常见的存储引擎和区别说明1. InnoDB2. MyISAM3. MEMORY4. A

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri