CPP教程-拓扑排序

CPP教程

拓扑排序（topsort）

例题ACWING848

const int N=1e5+5;
int h[N],nxt[N],to[N],cnt,du[N],n,m;

邻接表

void add(int a,int b)
{
    to[++cnt]=b;nxt[cnt]=h[a];h[a]=cnt;
}
int q[N],hh,tt;

拓扑排序

void topsort()
{
    for(int i=1;i<=n;i++)
      if(du[i]==0)
        q[++tt]=i;
    while(hh

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        du[b]++;
    }
    topsort();
    return 0;
}