Cod sursa(job #1314261)

Utilizator misu007Pogonaru Mihai misu007 Data 11 ianuarie 2015 17:51:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <queue>
using namespace std;

struct nod
{
    int x;
    nod* u;
}*a[50001];

int n,m,b[50001];
queue<int> q,s;

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int i,x,k=0;
    nod *q1;
    scanf("%d%d",&n,&m);
    while(m)
    {
        --m;
        q1=new nod;
        scanf("%d",&x);
        q1->u=a[x];
        a[x]=q1;
        scanf("%d",&x);
        q1->x=x;
        ++b[x];
    }
    for(i=1;i<=n;++i) if(!b[i]) q.push(i);
    while(!q.empty())
    {
        s.push(q.front());
        ++k;
        q1=a[q.front()];
        q.pop();
        while(q1)
        {
            --b[q1->x];
            if(!b[q1->x]) q.push(q1->x);
            q1=q1->u;
        }
    }
    if(k!=n) printf("Error");
    else
    {
        while(!s.empty())
        {
            printf("%d ",s.front());
            s.pop();
        }
        printf("\n");
    }
    return 0;
}