Cod sursa(job #591694)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 25 mai 2011 08:30:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
using namespace std;

typedef struct nod
{
    int inf;
    nod *urm;
} NOD;
typedef NOD *graf[50100];

graf G;
int n,m,gr[50100],c[50100];

ifstream f("sortaret.in");
ofstream g("sortaret.out");

void citire()
{
    NOD *p;
    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        gr[y]++;
        p=new NOD;
        p->urm=G[x];p->inf=y;G[x]=p;
    }
}

void rezolv()
{
    for(int i=1;i<=n;i++)
        if(!gr[i])
            c[++c[0]]=i;
    for(int i=1;i<=n;i++)
    {
        NOD *p=G[c[i]];
        while(p)
        {
            gr[p->inf]--;
            if(!gr[p->inf])
                c[++c[0]]=p->inf;
            p=p->urm;
        }
    }
}

int main()
{
    citire();
    rezolv();
    for(int i=1;i<=n;i++)
        g<<c[i]<<" ";
    g<<endl;
    f.close();
    g.close();
    return 0;
}