《确定比赛名次》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

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

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