[算法板子] 求拓扑序列（拓扑排序）

前言 / 导言

拓扑排序有多种求法，可用DFS、BFS求出，其中如果需要求出按字典序排列的拓扑序，则需要使用BFS将再将队列换为优先队列即可。

存图方法

用邻接表（链式向前星结构）存图，每个点的入度为d数组

int head[M], ne[N], to[N], idx, d[M];

bool st[M];

void add ( int a, int b )

{

d[b]++; // b 的入度加 1

to[idx] = b;

ne[idx] = head[a];

head[a] = idx++;

}

以下为拓扑排序的模板

模板一：优先队列法

优先队列中存的是点的编号

res容器中存的是最终答案

/* 邻接表（链式向前星）存图 */

void topsort ( int n, int m ) // 顶点数、边数

{

vector res;

priority_queue, greater > q;

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

{

if ( d[i] == 0 ) q.push ( i );

}

while ( !q.empty() )

{

int t = q.top(); q.pop();

res.push_back ( t ); // 记录拓扑序

for ( int i = head[t]; i != -1; i = ne[i] )

{

int b = to[i];

if ( --d[b] == 0 ) q.push ( b );

}

}

}

模板题：HDU1285

好题推荐：POJ1270