HDU 1285 确定比赛名次拓扑排序(邻接矩阵邻接表-白红宇

HDU 1285 确定比赛名次拓扑排序(邻接矩阵邻接表

阅读量：7287 次

发布时间：2019-06-30

本文共 2864 字，大约阅读时间需要 9 分钟。

确定比赛名次

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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 31 22 34 3

Sample Output

1 2 4 3 一开始是先用邻接矩阵做  这样做思路比较简单但是数据一大的话就会爆内存  而且比起邻接表也慢了很多

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 using namespace std;#define FIN freopen("input.txt","r",stdin);#define FOUT freopen("output.txt","w",stdout);#define INF 0x3f3f3f3f#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;const int MAXN=1000+5;int Map[MAXN][MAXN],cnt[MAXN];int main(){ //FIN int N,M,x,y; while(~scanf("%d%d",&N,&M)) { memset(Map,0,sizeof(Map)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=M;i++){ scanf("%d%d",&x,&y); if(Map[y][x]==0) cnt[y]++; Map[y][x]=1; } for(int i=1;i<=N;i++){ int j; for(j=1;j<=N;j++) {if(cnt[j]==0) break;} cnt[j]--; if(i

第二种是优化过的邻接表

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 using namespace std;#define FIN freopen("input.txt","r",stdin);#define FOUT freopen("output.txt","w",stdout);#define INF 0x3f3f3f3f#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;const int MAXN=1e5+5;/*判断一个有向图是否有环每次删除一个入度为0的点，直到没有入度为0的点为止。如果这时还有点没被删除，这些没被删除的点至少组成一个环；反之如果所有点都被删除了，则有向图中一定没有环。*/struct Edge{ int v,nxt;}E[MAXN*2];int Head[MAXN],erear;int IN[MAXN]; //记录入度int P[MAXN],sz; //打印用void edge_init(){ erear=0; memset(Head,-1,sizeof(Head)); memset(IN,0,sizeof(IN));}void edge_add(int u,int v){ E[erear].v=v; E[erear].nxt=Head[u]; Head[u]=erear++;}int main(){ //FIN int n,m; while(~scanf("%d%d",&n,&m)) { edge_init(); //初始化 for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); edge_add(u,v); IN[v]++; //v的入度+1 } sz=0; priority_queue
                  
                   
                    ,greater
                    
                      >Q; //这题要用到优先队列 for(int i=1;i<=n;i++){ if(!IN[i]) Q.push(i); //把入度为0的加入队列 } bool sign=0; //判断是否有多个结果 while(!Q.empty()){ if(Q.size()>=2) sign=1; int u=Q.top(); Q.pop(); P[sz++]=u; //把要打印的数加入P for(int i=Head[u];~i;i=E[i].nxt){ //普通遍历 int v=E[i].v; IN[v]--; //删边 if(!IN[v]) Q.push(v); //如果删边后新点入度为0加入队列 } } if(sz!=n){ //如果不可能的话 printf("invalid\n"); return 0; } /*if(sign){ printf("multi ans\n"); return 0; }*/ for(int i=0;i

转载于:https://www.cnblogs.com/Hyouka/p/5739070.html

你可能感兴趣的文章