Cod sursa(job #591691)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 25 mai 2011 08:25:06
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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<=n;i++)
    {
        f>>x>>y;
        gr[y]++;
        p=new NOD;
        p->urm=G[x];p->inf=y;G[x]=p;
    }
}

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

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