文章

14

粉丝

131

获赞

7

访问

28.5k

头像
确定比赛名次 题解:拓扑排序
P1566 中山大学2019年机试题
发布于2023年9月11日 17:15
阅读数 648

解题思路:拓扑排序裸题。所谓的拓扑排序就是将入度为0的节点编号入队(因题目要求输出编号小的队伍在前面,所以采用最小堆优先队列来维护条件),当队首元素出队时,依次以它为尾的弧的另一端节点入度减1,同样只要有节点的入度减完为0的就其入队,循环直至不存在无前驱的顶点。

当然此题不存在有向环,因为自己不会和自己比赛,虽然输入有可能出现重复数据即相同的有向边,但是出队的元素已经将其容器中的每个元素编号(即邻接点)的入度都减1,最后有多组相同重复的数据(即邻接点)的入度会减为0,这时入队就不存在有和之前相同的编号,所以不必担心因重边(有向边)而出现输出有相同的顶点编号。

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
vector<int> vec[maxn];//邻接表,每个节点保存与它相连的边的另一个端点
priority_queue<int, vector<int>,greater<int> >que;//最小堆优先队列
int n,m,u,v,num,InDeg[maxn];//记录每个节点的入度,num用来表示节点的个数
void topsort(){
    num=0;
    for(int i=1;i<=n;++i)
        if(!InDeg[i])que.push(i);//预处理,先将入度为0的节点编号入队
    while(!que.empty()){
        int now=que.top();que.pop();num++;
        cout<<now<<(num==n?"\n":" ");//同时输出
        for(unsigned int i=0;i<vec[now].size();++i)//遍历每个节点的相关连节点,一次循环可以将与now有边的多个重复点(还是该点)的入度减为0,这时就直接将其入队
            if(--InDeg[vec[now][i]]==0)que.push(vec[now][i]);
    }
}
int main()
{
    w...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发