杭州电子科技大学Online Judge 之 “确定比赛名次(ID1285)”解题报告

杭州电子科技大学Online Judge 之 “确定比赛名次(ID1285)”解题报告

大家好,又见面了,我是全栈君。

杭州电子科技大学Online Judge 确定比赛名次(ID1285解题报告
巧若拙(欢迎转载,但请注明出处:http://blog.csdn.net/qiaoruozhuo

 

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

 

算法分析: 

本题是拓扑排序的典型应用。

因为顶点数量不多,能够採用邻接矩阵来存储图信息,这样算法比較简单,仅仅须要搜索n次,每次把序号最小的入度为0的顶点存储到拓扑序列中即可了。算法思路比較清晰。代码也比較简洁。但时间复杂度和空间复杂度都较高。

还有一种方法是採用邻接表存储图信息。因为题目要求输出时编号小的队伍在前,所以在入栈时一定要保证先让序号最小的入度为0的顶点在栈顶,这样依据后进先出的特点,能够把序号最小的顶点存储到拓扑序列中。我採用折半插入排序的方法。把入度为0的顶点按递减序排序,然后对图进行深度优先搜索,能获得正确的拓扑序列。

本算法时间复杂度和空间复杂度都非常好。可是代码较长。

两种算法都给出代码,大家能够比較一下。并请提出宝贵意见。

说明: 

算法思想:拓扑排序,折半插入。

数据结构:邻接矩阵。邻接表。

时间复杂度:算法1O(N^2);当中N为顶点数量;

       算法2O(N+M);当中N为顶点数量。M为边的数量

 

空间复杂度:算法1O(MAXN^2);当中MAXN为最大顶点数量;

算法2O(MAXN +M);当中MAXN为最大顶点数量;M为边的数量。

Run ID

Submit Time

Judge Status

Pro.ID

Exe.Time

Exe.Memory

Code Len.

Language

Author

 

12236157

2014-11-19 14:09:06

Accepted

1285

31MS

1232K

C

巧若拙

12235820

2014-11-19 13:07:33

Accepted

15MS

460K

4004 B

C

巧若拙

 

代码例如以下:

算法1

#include<stdio.h>

#include<stdlib.h>

 

#define MAXN 502   //最大顶点数量

 

int map[MAXN][MAXN] = {0};

 

void TopoLogicalSort(int n);

 

int main()

{

    int i, j, m, n, u, v;

 

    while(scanf(“%d%d”, &n,&m) != EOF)

       {  

           for (i=0; i<MAXN;i++)

                  for (j=0; j<MAXN; j++)

                         map[i][j] = 0;

          

              for (i=0; i<m; i++)       

              {

                     scanf(“%d%d”, &u, &v);

                     if (map[u][v] == 0)    //数据可能会反复

                     {

                            map[u][v] = 1;

                            map[0][v]++; //存储顶点v的入度

                     }

              }

             

              TopoLogicalSort(n);

    }

        

    return 0;

}

 

void TopoLogicalSort(int n)

{

    int i, j, top;

    int topo[MAXN] = {0};

   

    for (top=0; top<n; top++)//总共同拥有n个顶点,搜索n

    {

           for(i=1; i<=n; i++)//寻找入度为0的序号最小的顶点

           {

                  if(map[0][i] == 0)

                  {

                         map[0][i]= -1;

                         break;

                  }

           }

           topo[top]= i;

           for(j=1; j<=n; j++) //弧尾i相应弧头j入度减1

           {

                  if(map[i][j] == 1)

                         map[0][j]–;

           }

    }

   

    for (i=0; i<top-1; i++)

    {

           printf(“%d”, topo[i]);

    }

    printf(“%d\n”, topo[top-1]);

}

 

算法2

#include<stdio.h>

#include<stdlib.h>

 

#define MAXN 510   //最大变量(顶点)数量

 

typedef int VertexType; //顶点类型由用户自己定义

typedef int EdgeType; //边上的权值类型由用户自己定义

 

typedef struct EdgeNode{ //边表结点

    int adjvex; //邻接点域,存储该顶点相应的下标

//    EdgeType weight; //权值,对于非网图能够不须要

    struct EdgeNode *next; //链域,指向下一个邻接点

} EdgeNode;

 

typedef struct VertexNode{ //顶点表结点

    VertexType data; //顶点域,存储顶点信息

    int in;  //存储顶点入度的数量

    EdgeNode *firstEdge; //边表头指针

} VertexNode;

 

void CreateGraph(VertexNode*GL, int n, int m);//把顶点和边信息读入到表示图的邻接表中

int InsertStack(int vec[],int x, int n);//折半插入,递减排序

voidTopoLogicalSort_DFS(VertexNode *GL, int n);

 

int main()

{

    int i, m, n;

    VertexNode GL[MAXN];

   

    while(scanf(“%d%d”, &n,&m) != EOF)

       {  

           CreateGraph(GL, n,m);//把顶点和边信息读入到表示图的邻接表中

          TopoLogicalSort_DFS(GL, n);

    }

        

    return 0;

}

 

void CreateGraph(VertexNode*GL, int n, int m)//把顶点和边信息读入到表示图的邻接表中

{

    int i, u, v;

    EdgeNode *e;

 

    for (i=1; i<=n; i++)//初始化图

    {

        GL[i].data = i;

        GL[i].in = 0;

        GL[i].firstEdge = NULL;

    }

   

    for (i=0; i<m; i++)

    {

        e = (EdgeNode*)malloc(sizeof(EdgeNode));//採用头插法插入边表结点

        if (!e)

        {

            puts(“Error”);

            exit(1);

        }

       

        scanf(“%d%d”, &u,&v);

        e->next = GL[u].firstEdge;

        GL[u].firstEdge = e;

        e->adjvex = v;

        GL[v].in++;

    }

}

 

int InsertStack(int vec[],int x, int n)//折半插入,递减排序

{

       int low = 0, high = n – 1, mid, j;

 

    while(low <= high) //折半查找插入位置

    {

              mid = (low + high)/2;

              if(vec[mid] < x)

              {

                     high = mid -1;

              }

              else

              {

                     low = mid + 1;

              }

       }

    //进行插入操作

    for(j=++n; j>low; j–)

    {

        vec[j] = vec[j-1];

    }

    vec[low] = x;

   

    return n;

}

 

voidTopoLogicalSort_DFS(VertexNode *GL, int n)

{

    int i, u, v, top = 0;

    int count = 0;

    EdgeNode *e;

    int topo[MAXN], Stack[MAXN];//有序栈(或优先队列)

   

    for (i=1; i<=n; i++)//将入度为0的顶点按序号大小逆序入栈

    {

        if (GL[i].in == 0)

        {

             top = InsertStack(Stack, i, top);

        }

    }

    

    while (top > 0)//採用深度优先搜索获取拓扑序列

    {

        u = Stack[–top];

        topo[count++] = u;

       

        for (e=GL[u].firstEdge; e!=NULL;e=e->next)//u的邻接点入度减1,并将入度为0的顶点入栈

        {

            v = e->adjvex;

            if (–GL[v].in == 0)

            {

                   top= InsertStack(Stack, v, top);

            }

        }

    }

   

    for (i=0; i<count-1; i++)

    {

           printf(“%d”, topo[i]);

    }

    printf(“%d\n”, topo[count-1]);

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115972.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 有赞和腾讯云、阿里云一同摘得“中国企业云科技服务商50强”[通俗易懂]

    有赞和腾讯云、阿里云一同摘得“中国企业云科技服务商50强”[通俗易懂]互联网时代的每一次技术变革都带来新的机会,而云计算这一诞生于2006年的新技术正在引领新的科技浪潮。正是从2006年开始,众多云计算公司借助云计算的东风,成长为数十亿、上百亿甚至超千亿美元市值的科技公司。亚马逊就是在2006年转向云计算之后,用十年时间成长为一家万亿美元市值的公司。在亚马逊之后,Salesforce也稳稳站上了千亿美元市值。而ServiceNow、Workday、Veeva、Shopify则在向500亿美元关口冲刺。紧随其后的是大量数十亿美元市值的云计算公司,它们分布在企业服务的…

  • deepfakes怎么用_黑科技▍如何使用 Deepfakes 给主播换脸?教程来了

    deepfakes怎么用_黑科技▍如何使用 Deepfakes 给主播换脸?教程来了下面放教程:1.获取deepfakes工具包gitclonehttps://github.com/deepfakes/faceswap.git2.补齐依赖包:pipinstalltqdmpipinstallcv2pipinstallopencv-contrib-pythonpipinstalldlibpipinstallkeraspipinstalltensorfl…

  • 旷望(2018年党建工作)

    全球计算机视觉顶会CVPR2018(ConferenceonComputerVisionandPatternRecognition,即IEEE国际计算机视觉与模式识别会议)将于6月18日至22日在美国盐湖城举行。作为大会钻石赞助商,旷视科技Face++研究院也将在孙剑博士的带领下重磅出席此次盛会。而在盛会召开之前,旷视将针对CVPR2018收录论文集中进行系列解读。…

  • 2023电子科技大学计算机考研信息汇总及答案_计算机考研难度排行榜

    2023电子科技大学计算机考研信息汇总及答案_计算机考研难度排行榜N诺小程序-计算机学习考研必备神器电子科技大学计算机科学与工程学院电子科技大学信息与软件工程学院电子科技大学基础与前沿研究院电子科技大学电子科学技术研究院电子科技大学通信抗干扰技术国家级重点实验室电子科技大学数学科学学院电子科技大学(UniversityofElectronicScienceandTechnologyofChina)坐落于四川省会成都市,直属中华人民共和国教育部,由教育部、工业和信息化部、四川省和成都市共建。是国家“…

  • CES Asia专题|用眼睛控制一切,青研科技带来新一代人机交互方式

    CES Asia专题|用眼睛控制一切,青研科技带来新一代人机交互方式

  • 【金融科技前沿】【长文】金融监管、监管科技以及银行业监管报送概述「建议收藏」

    【金融科技前沿】【长文】金融监管、监管科技以及银行业监管报送概述「建议收藏」上周金融科技前沿课程的主题是《监管科技》,韩海燕老师从金融监管引入,介绍了我国的金融监管体系,接着进入监管科技的详细讲解。我觉得最主要的是弄清楚监管科技的定义,以及在实际的银行业应用场景中具体的运作流程是怎么样的。韩老师讲的很全面,将ABCD等金融科技手段在监管系统中是如何运作的讲的很清楚,收获颇丰,但是比较少涉及到监管的对象和内容,仍没有很清楚监管机构是要监管什么东西?监管机构要求银行金融业机构报送的资料有哪些?这些报送要求的目的分别是什么?所以这篇文章分为三个部分,一是介绍金融监管,二是介绍监科技,三.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号