拓扑排序
_Cheems
·
2023-07-16 09:09:46
·
个人记录
基础概念
在一个有向图中，将所有点排序得到一个序列。对于任意点，使得所有指向它的点都在序列中比它提早出现，则该序列称为拓扑序列。
这么说不太好懂，举个栗子：
上图的拓扑序列是：4、1、3、2。
求拓扑序列的意义
当题目是求有向图（可能有环）中从 u 到 v 的不同路径时，我们可以求出它的拓扑序列，然后 DP 求解。
总之，求出有向图的拓扑序列，就能把它化为 DAG，便于求解。
拓扑排序
得到拓扑序列的算法称作拓扑排序，下面是主要思路：
首先，将入度为 0 的点加入队列，因为它们一定在序列开头。
然后遍历队列中的每个点，将它所指向的点的入度减 1，这样又得到一些入度为 0 的点，以此类推直到遍历完所有的点。
还是那张图，首先，把 4 加入队列，删去以它为发端的边：
此时 1 的入度又变为 0，重复上面的操作：
记录删点的次序，得到拓扑序列 4、1、3、2。
显然，遍历队列中点的次序不同，便会得到不同的拓扑序列，求出其一即可。
代码：
for(int i=1; i<=n;i++)
{
if(ru[i]==0)
{
q.push(i);
}
}
for(int i=1; i<=n;i++)
{
int u=q.front();
topu[++cnt]=u;
q.pop();
for(int j=0; j { int v=edge[u][j]; ru[v]--; if(ru[v]==0) { q.push(v); } } }