拓扑排序（C++）

  拓扑排序是指对有向无环图中的所有结点进行排序的一种算法。拓扑排序依赖于图的拓扑结构，即顶点之间的依赖关系。拓扑排序的过程类似于排课，每个课程都有其先修课程，只有当其先修课程修完了，该课程才能开始学习。

拓扑排序通过遍历节点的入度（入边的数量）来判断结点之间的依赖关系，从而对所有结点进行排序。具体过程如下：

1. 找到所有入度为0的结点，将其入队。

2. 取出队首结点，将其加入结果列表。

3. 将该结点指向的所有结点的入度减1。

4. 遍历所有入度为0的结点，将其加入队列中。

5. 重复步骤2-4，直到队列为空。

#include
#include
#include
using namespace std;
int n, d[10000] = { 0 }, ans[10000],k;//节点,节点入度数，储存图，储存答案
vector<int> g[100];
void topusort()
{
	queue<int> q;//入度为0的队列
	for (int i = 1; i <= n; i++)//将入度为0的点进入队列
	{
		if (d[i] == 0)
			q.push(i);
	}
	while (!q.empty())//队列不为空
	{
		int f = q.front();//取队头
		ans[k++] = f;
		q.pop();
		for (int i = 0; i < g[f].size(); i++)
		{
			int t = g[f][i];
			d[t]--;//与f有连接的点，入度减一
			if (d[t] == 0)//度为0的点进入队列
				q.push(t);
		}
	}
 
}
int main()
{
	cin >> n;//节点数
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;
		d[y]++;//y点入度加一
		g[x].push_back(y);//用vector存图
	}
	topusort();
	if (k != n)
		cout << "图中有环，无法进行" << endl;
	else
	{
		cout << "拓扑排序后序列：" << endl;
		for (int i = 0; i < k; i++)
			cout << ans[i];
	}
}