【拓扑排序】排队C++

描述

今天,学校老师让同学们排成一队,准备带大家出去玩,一共有 n 名同学,排队的时候同学们向老师提了 m 条要求,每一条要求是说同学 x 一定要排在同学 y 之前,老师现在想找到一种排队方式可以满足所有的要求,你能帮帮他吗?


输入
第一行两个整数 n,m(1≤n≤10^410 
4
 ,1≤m≤10^510 
5
 ),表示同学数和要求数;

以下 m 行,每行两个整数 x,y,之间用一个空格隔开,表示某个要求是第 x 号同学要排在第 y 号同学之前,所有同学的编号由 1 开始;

输入保证有解。


输出
输出一行,包括 n 个整数,表示从前往后同学的编号,用空格隔开,如果答案不唯一,输出字典序最小的答案。


输入样例 1 

2 1
1 2
输出样例 1

1 2
提示

提示:使用优先队列进行拓扑排序

一道拓扑排序模板题,大概掌握了写法就可以a,要注意的是优先队列的写法,参照下面代码(咳咳同机房(?)大佬的代码)

#include<bits/stdc++.h>
using namespace std;

const int MAX_N=20000;
const int MAX_M=200000;
int ans[20000],cnt;
struct edge{
	int v,next;
	int len;
}E[MAX_M];
int p[MAX_N],eid;
void init(){
	memset(p,-1,sizeof(p));
	eid=0;
}
void insert(int u,int v){
	E[eid].v=v;
	E[eid].next=p[u];
	p[u]=eid++;
}
int n,m;
int indegree[MAX_N];
priority_queue<int,vector<int>,greater<int> > q;
void topo(){
	//queue<int> q;
	for(int i=1;i<=n;i++){
		if(indegree[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int now=q.top();
		cnt++;
		ans[cnt]=now;
		q.pop();
		for(int i=p[now];i!=-1;i=E[i].next){
			int v=E[i].v;
			indegree[v]--;
			if(indegree[v]==0){
				q.push(v);
			}
		}
	}
}
int main(){
	init();
	memset(indegree,0,sizeof(indegree));
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		insert(u,v);
		indegree[v]++;
	}
	topo();
	for(int i=1;i<=cnt;i++){
		cout<<ans[i];
		if(i<cnt){
			cout<<" ";
		}
	}
	return 0;
}

ov.

个人博客地址: www.moyujiang.com 或 moyujiang.top
原文地址:https://www.cnblogs.com/moyujiang/p/11167795.html