拓扑排序模板

_pzy · 2025-01-21 14:49:56 · 算法·理论

代码

拓扑排序

#include<bits/stdc++.h>
using namespace std;
int n,m,flag,x,y,z,head[4000005],cnt,b[100005];
queue<int> c;
struct abc
{
    int to,next;
}a[8000005];
void add(int x,int y)
{
    cnt++;
    a[cnt].next=head[x];
    head[x]=cnt;
    a[cnt].to=y;
    b[y]++;
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==0)
        {
            c.push(i);
        }
    }
    while(!c.empty())
    {
        int t=c.front();
        cout<<t<<" ";
        c.pop();
        b[t]=-1;
        for(int i=head[t];;i=a[i].next)
        {
            if(i==0)
            {
                break;
            }
            b[a[i].to]--;
            if(b[a[i].to]==0)
            {
                c.push(a[i].to);
            }
        }
    }
    return 0;
}

优先队列+拓扑排序

#include<bits/stdc++.h>
using namespace std;
int n,m,flag,x,y,z,head[4000005],cnt,b[100005];
priority_queue<int,vector<int>,greater<int> > c;
struct abc
{
    int to,next;
}a[8000005];
void add(int x,int y)
{
    cnt++;
    a[cnt].next=head[x];
    head[x]=cnt;
    a[cnt].to=y;
    b[y]++;
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==0)
        {
            c.push(i);
        }
    }
    while(!c.empty())
    {
        int t=c.top();
        cout<<t<<" ";
        c.pop();
        b[t]=-1;
        for(int i=head[t];;i=a[i].next)
        {
            if(i==0)
            {
                break;
            }
            b[a[i].to]--;
            if(b[a[i].to]==0)
            {
                c.push(a[i].to);
            }
        }
    }
    return 0;
}