Cod sursa(job #751146)

Utilizator alexalbu95Albu Alexandru alexalbu95 Data 24 mai 2012 17:29:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
// sortare topologica cu BFS - alocare dinamica
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int i, st, dr, x, n, m, d[50001], U[50001], C[50001];

struct point{
    int info;
    point *urm;
};
point *G[50001];

void add(int x, int y)
{
    point *p;

    p=new point;
    p->info=y;
    p->urm=G[x];
    G[x]=p;
}

void citire()
{
    int x, y;
    f>>n>>m;
    for(m; m; --m)
    {
        f>>x>>y;
        add(x, y);
        d[y]++;
    }
}

int main()
{
    citire();
    for(i=1; i<=n; ++i)
        if(!d[i]) { C[++dr]=i; U[i]=1; }

    point *p;

    for(st=1; st<=dr; ++st)
    {
        x=C[st];
        for(p=G[x]; p; p=p->urm)
        {
            d[p->info]--;
            if(!d[p->info] && !U[p->info])
            {
                C[++dr]=p->info;
                U[p->info]=1;
            }
        }
    }
    for(i=1; i<=n; ++i) g<<C[i]<<" ";
}