拓扑排序

算法学习笔记(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\)。 [[B3644 拓扑排序 & 家谱树 - 洛谷]][B3644 【模板】拓扑排序 / 家谱树 - 洛谷](https://www.luogu.com.cn/problem/B3644) 练习： [[510C]] Problem - C - Codeforces