拓扑排序

核心理解

每次取一个入度为 0 的点，说明它没有尚未完成的前置依赖；删除它的出边后，新的入度为 0 的点也可以入队。若最终输出数量小于 n，图中存在环，无法拓扑排序。

• 复杂度：O(n + m)。
• 适用：课程依赖、任务调度、有向无环图（DAG）。
• 注意：答案不唯一；队列改成优先队列可得到字典序更小的方案。

模板代码

#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int maxn=1e5;
int to[maxn],ne[maxn], h[maxn],idx,in[maxn];
void add(int a, int b)
{
    to[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
    in[b]++;
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for (int i=1;i<=n;i++)
    {
        int m;
        cin>>m;
        while (m!=0)
        {
            add(i,m);
            cin>>m;
        }
    }
    queue<int>q;
    for (int i=1;i<=n;i++)
    {
        if (in[i]==0)
        {
            q.push(i);
        }
    }
    while (q.size())
    {
        int u=q.front();
        q.pop();
        cout<<u<<' ';
        for (int i=h[u];i!=-1;i=ne[i])
        {
            int j=to[i];
            in[j]--;
            if (in[j]==0)
            {
                q.push(j);
            }
        }
    }
    return 0;
}

‍