文章
14
粉丝
132
获赞
7
访问
33.5k
解题思路:拓扑排序裸题。所谓的拓扑排序就是将入度为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...
登录后发布评论
暂无评论,来抢沙发