拓扑排序专题1 拓扑排序

题目：

样例：

输入
`4 5 0 1 0 2 0 3 1 2 3 2`

输出
0 1 3 2

思路：

拓扑序列含义
一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)(x,y)， x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

而拓扑序列当中可以有多种合法的拓扑序列，其中无向图不存在拓扑序列。

由于有多种合法的拓扑序列，所以题目要求选择编号最小的结点排序。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

int n,m;

umap<int,int>d,arr;	// 记录存储所有结点的入度数量

// 数组模拟链表
int h[N],e[N],ne[N],idx;
inline void Add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

inline void topoSort()
{
	// 建立优先队列，优先选着编号小的结点拓扑排序
	priority_queue<int,vector<int>,greater<int>>q;
	
	// 选择入度为 0 的结点作为最前面的起点
	for(int i = 0;i < n;++i)
	{
		if(!d[i]) q.emplace(i);
	}
	
	// 开始 topoSort 搜索
	while(q.size())
	{
		// 选择当前走动搜索到的结点
		int now = q.top();
		q.pop();
		
		arr[idx++] = now;	// 存储当前结点作为的拓扑结点
		
		// 遍历当前结点所连接到的结点
		for(int i = h[now];i != -1;i = ne[i])
		{
			int j = e[i];	// 获取连接的结点
			if(d[j]) --d[j];	// 删除对应结点的 入度边
			
			if(!d[j]) q.emplace(j);	// 如果该入度数为 0 之后，说明可以选择作为拓扑序列
		}
	}
}

inline void solve()
{
	// 初始化链表头
	memset(h,-1,sizeof h);
	cin >> n >> m;
	while(m--)
	{
		int a,b;
		cin >> a >> b;
		Add(a,b);	// 连接图
		++d[b];		// 记录相应结点的入度
	}
	
	idx = 0;	// 重复利用一下下标
	
	topoSort();	// 开始拓扑排序
	
	for(int i = 0;i < idx;++i)
	{
		if(i) cout << ' ';
		cout << arr[i];
	}
	
}

int main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}