拓扑排序

拓扑排序

对一个有向无环图(Directed Acyclic Graph,DAG)G进行拓扑排序，是将G中的结点排成一个线性序列，使得图中任意一对顶点u和v，若有边<u,v>属于E(G)，则u在序列中必须出现在v前面。所有结点满足这样的条件得出的线性序列称为拓扑次序的序列，简称拓扑排序。
需要的变量除了边之外，还要设置一个in[]数组，in[i]表示当前i结点的入度。
板子

vector<int> edge[n];
void topu(){
    queue<int> q;
    for (int i=1;i<=n;i++)   if (in[i]==0)
        q.push(i);
    while (!q.empty()){
        int temp = q.front();   q.pop();
        for (int i=0;i<edge[temp].size();i++){
            in[edge[temp][i]]--;
            if (in[edge[temp][i]]==0)
                q.push(edge[temp][i]);
        }
    }
    return;
}

若要求按字典序排序时，将队列换成优先队列即可。
拓扑排序在AC自动机、回文自动机(PAM)里的fail树上会用到。