Cod sursa(job #1145846)

Utilizator misu007Pogonaru Mihai misu007 Data 18 martie 2014 14:43:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <queue>
using namespace std;

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

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

void solve()
{
    int i;
    nod *nou;
    for(i=1;i<=n;++i) if(!g[i]) q.push(i);
    while(!q.empty())
    {
        nou=a[q.front()];
        while(nou)
        {
            g[nou->x]--;
            if(!g[nou->x]) q.push(nou->x);
            nou=nou->u;
        }
        s.push(q.front());
        q.pop();
    }
}

void read()
{
    int x,y,m;
    nod* nou;
    freopen("sortaret.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(m)
    {
        --m;
        scanf("%d%d",&x,&y);
        nou=new nod;
        nou->u=a[x];
        a[x]=nou;
        a[x]->x=y;
        g[y]++;
    }
}

void write()
{
    freopen("sortaret.out","w",stdout);
    while(!s.empty())
    {
        printf("%d ",s.front());
        s.pop();
    }
    printf("\n");
}

int main()
{
    read();
    solve();
    write();
    return 0;
}