确定比赛名次（拓扑排序）

清疚 2022-08-02 01:29 155阅读 0赞

![20150705134445245][]

**这一题是典型的拓扑排序题目！需要注意的两点就是可能有重复**

**边，所以你要学会过滤重复边！还有就是定义变量要在main函数**

**之外定义，否则压栈，就爆栈了，以后要注意这个问题了！**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    const int maxs=510;
    using namespace std;
    int num[maxs],f,n;
    int mp[maxs][maxs],indegree[maxs];
    void toposort(int mp[maxs][maxs],int indegree[maxs],int n)
    {
        int i,j,k;
        for(i=1;i<=n;i++)//遍历N次
        {
            for(j=1;j<=n;j++)//找出入读为0的节点
            {
                if(indegree[j]==0)
                {
                    indegree[j]--;
                    num[f++]=j;
                    for(k=1;k<=n;k++)
                    {
                        if(mp[j][k]==1)//有关系！
                        {
                            indegree[k]--;
                        }
                    }
                    break;
                }
            }
        }
         for(i=0;i<f-1;i++)
         {
            cout<<num[i]<<" ";
         }
         cout<<num[f-1]<<endl;
    }
    int main()
    {
        int m,i,a,b;
        while(cin>>n>>m)
        {
            f=0;
            memset(mp,0,sizeof(mp));
            memset(indegree,0,sizeof(indegree));
            for(i=1;i<=m;i++)
            {
                cin>>a>>b;
                if(mp[a][b]==0)//过滤重复边
                {
                    mp[a][b]=1;
                    indegree[b]++;
                }
            }
            toposort(mp,indegree,n);
        }
    }

[20150705134445245]: /images/20220731/051df29fc95f4eba9ef09f36fc0ff3b8.png

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关确定比赛名次拓扑排序 + 优先队列

<table> <tbody> <tr> <td> <h2>确定比赛名次</h2> <strong>Time Limit: 2000/1000 MS (Jav

朱雀/ 2024年02月18日 22:58/ 0 赞/ 58 阅读

相关拓扑排序学习小记 HDU 1285 确定比赛名次 + HDU 2647 Reward

拓扑排序，以下摘自http://blog.csdn.net/midgard/article/details/4101025：拓扑排序是对有向无环图(DAG图)的一种排序。表

落日映苍穹つ/ 2022年08月25日 08:46/ 0 赞/ 111 阅读

相关杭电-1285确定比赛名次(topo)

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

今天药忘吃喽~/ 2022年08月10日 08:37/ 0 赞/ 81 阅读

相关 hdoj 1285 确定比赛名次【拓扑】

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

秒速五厘米/ 2022年08月04日 13:44/ 0 赞/ 105 阅读

相关确定比赛名次（拓扑排序）

![20150705134445245][] 这一题是典型的拓扑排序题目！需要注意的两点就是可能有重复边，所以你要学会过滤重复边！还有就是定义变量要在main函

清疚/ 2022年08月02日 01:29/ 0 赞/ 156 阅读

相关【杭电1285】确定比赛名次

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

ゞ浴缸里的玫瑰/ 2022年07月18日 16:24/ 0 赞/ 141 阅读

相关拓扑排序

在这里我们引入AOV（Activity-On-Vertex）网，图的顶点代表活动，其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。对于一个工程，我们首先将这

野性酷女/ 2022年06月10日 13:28/ 0 赞/ 198 阅读

相关确定比赛名次

确定比赛名次有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能

男娘i/ 2022年05月15日 05:58/ 0 赞/ 154 阅读

相关杭电 1285 确定比赛名次（直接拓扑排序）

Problem Description 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次

绝地灬酷狼/ 2021年12月20日 08:55/ 0 赞/ 142 阅读

相关拓扑排序

作用：判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 478 阅读