【模板】拓扑排序

xxxasybt2023 · 2025-10-23 21:28:26 · 算法·理论

vector版

void topsort(int n,vector<int> *g,int *in,int *ans,bool icd)
{
    queue<int,list<int> > q;int len = 0,t;
    if (!icd) for (int i = 1;i <= n;i ++) for (auto j:g[i]) in[j] ++;
    for (int i = 1;i <= n;i ++) if (!in[i]) q.push(i);
    while (!q.empty())
    {
        t = q.front(),q.pop(),ans[++len] = t;
        for (auto i:g[t]) if (--in[i] == 0) q.push(i);
    }
}

链式前向星版

前置知识：链式前向星

void topsort(int n,LFS g,int *in,int *ans,bool icd)
{
    queue<int,list<int> > q;int len = 0,t;
    if (!icd) for (int i = 1;i <= n;i ++) for (int j = g.head[i];j;j = g.edge[j].ne) in[g.edge[j].to] ++;
    for (int i = 1;i <= n;i ++) if (!in[i]) q.push(i);
    while (!q.empty())
    {
        t = q.front(),q.pop(),ans[++len] = t;
        for (int i = g.head[t],v;i;i = g.edge[i].ne) if (--in[v = g.edge[i].to] == 0) q.push(v);
    }
}