Cod sursa(job #908390)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 9 martie 2013 13:00:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct node
{
    int nr;
    node *next;
} *succ[50001];

int n,m,i,pred[50001],queue[50001],p,u,x,y;
node *d;

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y;
        pred[y]++;
        d=new node;
        d->nr=y;
        d->next=succ[x];
        succ[x]=d;
    }
    p=1;
    for (i=1;i<=n;i++) if (pred[i]==0) queue[++u]=i;
    while (p<=u)
    {
        x=queue[p];
        for (d=succ[x];d!=NULL;d=d->next)
        {
            pred[d->nr]--;
            if (pred[d->nr]==0) queue[++u]=d->nr;
        }
        p++;
    }
    for (i=1;i<=n;i++) fout<<queue[i]<<" ";
}