(拓扑排序)

在我们所学的课程中，部分课程之间可能存在依赖关系，如我们在学习图论知识之前，需要先学习离散数学中的基础知识。一门课可能有若干先修课程。现在李老师需要安排一些课程的授课计划，排课需要遵从一定的规则,即只有修习完某课程的全部课程后，才能修习该课程。

在本例中,用1~n表示n个课程,用x y表示x是y的先修课程，输入数据保证图中没有环与重边。要求输出任意一个可行的授课顺序。图用邻接矩阵方法储存。

#include <iostream>


#include <cstring>


# include <queue>


using namespace std;


const int N=105;


int a[N][N];


int in[N],s[N];


int n,m,u,v;


void Topo() {


	queue<int> q;


	int cnt;


	for(int i=1; i<=n; i++)


		if(___(1)___)


			q.push(i);


	while(!q.empty()) {


		int cur = q.front();


		q.pop();


		s[cnt++]=___(2)___;


		for (int i=1; i<=n; i++) {


			if (___(3)___) {


				___(4)___;


				if (in[i]==0)


					q.push(i);


			}


		}


	}


}


int main() {


	memset(in,0,sizeof(in));


	memset(a, 0,sizeof(a));


	cin>>n>>m;


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


		cin>>u>>v;


		in[v]++;


		___(5)___;


	}


	Topo();


	for (int i=0; i<n; i++) {


		if (i)


			cout<<' ';


		cout<<s[i];


	}


	cout<<endl;


	return 0;


}

选择题