拓扑排序

算法学习笔记(53): 拓扑排序 - 知乎

以下是一个 $O(n+m)$ 的实现（ $n,m$ 分别表示点数和边数），利用了队列：
一般使用的是邻接表存储图

// deg 是入度，在存图的时候需要录入数据
// A 是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort (int n)
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!deg[i])
            q.push (i);
    while (!q.empty ())
    {
        int t = q.front ();
        q.pop ();
        A[cnt++] = t;
        for (auto to : edges[t])
        {
            deg[to]--;
            if (!deg[to]) // 出现了新的入度为 0 的点
                q.push (to);
        }
    }
    return cnt == n;
}

返回值为是否成功进行拓扑排序，也即是否存在环。也就是说拓扑排序是可以用来简单地判环的。有时会要求输出字典序最小的方案，这时把 queue 改成 priority_queue 即可，复杂度会多一个 $\log$。
../../ACMExercises/Luogu/B3644 拓扑排序 & 家谱树 - 洛谷B3644 【模板】拓扑排序 / 家谱树 - 洛谷
练习：
../../ACMExercises/CodeForces/510C Problem - C - Codeforces