拓扑排序：可以对有向图的数据按照先后顺序进行排序，也可以用来检测有向图中有没有环

题目

课程表

题目描述

你这个学期必须选修n门课程，记为0到n-1。在选修某些课程之前需要一些先修课程。给你一个数组p，其中p[i]=[ai,bi]表示如果想选修课程ai，则必须先选修课程bi。m表示数组p中数据个数

例如，想要学习课程0，你需要先完成课程1，我们用一个匹配来表示:[0,1]。

先输入n、m，再输入数组p。
请你判断是否可能完成所有课程的学习?如果可以，返回true;否则,返回false。

样例

输入：

2 2

1 0

0 1

输出

false

解释:课程1需要先学0，课程0又需要先学1，存在循环依赖，不可能完成。

代码

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

int a[1010][1010];//邻接矩阵
int c[1010];//入度
int b[1010];//是否被访问
int r[1010];//排序结果
int lr;
int n,m;
queue<int> q;


void bfs();

int main()
{
	cin>>n>>m;
	for(int i = 0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[y][x] = 1;//构建邻接矩阵
		c[x]++;//增加入度的数量
	}
	
	bfs();
	
	if(lr==n) cout<<"true";
	else cout<<"false";
	
	
	
	
	return 0;
}
void bfs()
{
	for(int i = 0;i<n;i++)
	{
		if(c[i]==0)//入度等于0
		{
			q.push(i);
			b[i] = 1;//标记已被访问
			r[lr] = i;//排序
			lr++;
		}
	}
	while(q.empty()==false)
	{
		int head = q.front();
		q.pop();
		for(int i = 0;i<n;i++)
		{
			if(a[head][i]==1&&b[i]==0)
			{
				c[i]--;
				if(c[i]==0)
				{
					q.push(i);
					b[i] = 1;//标记已被访问
					r[lr] = i;//排序
					lr++;
				}
			}
		}
	}
}

课程表二

题目描述

现在你总共有n门课，编号为0到n-1。给你一个数组p，其中p[i=[ai,bi表示如果你想选修课程ai，则必须先完成课程bi。例如，[0,1]表示要选修课程0，必须先选修课程1。返回一种修完所有课程的顺序(可能存在多种有效顺序，你只需要返回其中一种)。如果不可能完成所有课程，返回一个空数组。m表示数组p中数据个数。

先输入n、m，再输入数组p。

样例

输入

4 4

1 0

2 0

3 1

3 2

输出

0 1 2 3 

（0 2 1 3 也可以）

代码

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

int a[1010][1010];//邻接矩阵
int c[1010];//入度
int b[1010];//是否被访问
int r[1010];//排序结果
int lr;
int n,m;
queue<int> q;


void bfs();

int main()
{
	cin>>n>>m;
	for(int i = 0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[y][x] = 1;//构建邻接矩阵
		c[x]++;//增加入度的数量
	}
	
	bfs();
	
	if(lr==n)
	{
		for(int i = 0;i<lr;i++)
		{
			cout<<r[i]<<" ";
		}
	}
	else
	{
		cout<<0;
	}
	
	
	
	
	return 0;
}
void bfs()
{
	for(int i = 0;i<n;i++)
	{
		if(c[i]==0)//入度等于0
		{
			q.push(i);
			b[i] = 1;//标记已被访问
			r[lr] = i;//排序
			lr++;
		}
	}
	while(q.empty()==false)
	{
		int head = q.front();
		q.pop();
		for(int i = 0;i<n;i++)
		{
			if(a[head][i]==1&&b[i]==0)
			{
				c[i]--;
				if(c[i]==0)
				{
					q.push(i);
					b[i] = 1;//标记已被访问
					r[lr] = i;//排序
					lr++;
				}
			}
		}
	}
}