Cod sursa(job #1700458)

Utilizator AstelonBanica Mihai Astelon Data 10 mai 2016 16:07:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>

using namespace std;

struct lista;

struct elem
{
    int info;
    elem *urm;
    elem()
    {
        info=-1;
        urm=NULL;
    }
    ~elem()
    {
        if(urm!=NULL)
            delete urm;
    }
    friend lista;
};

struct lista
{
    elem *urm,*u;
    lista()
    {
        urm=NULL;
        u=NULL;
    }
    ~lista()
    {
        if(urm!=NULL)
            delete urm;
    }
};

void dfstop(lista *l[50001],int x,int a[50001],bool v[50001],int &nr)
{
    v[x]=1;
    elem *p;
    for(p=l[x]->urm;p!=NULL;p=p->urm)
    {
        if(v[p->info]==0)
            dfstop(l,p->info,a,v,nr);
    }
    a[nr--]=x;
}

int main()
{
    int n,m,i;
    lista *l[50001];
    ifstream f("sortaret.in");
    f>>n>>m;
    for(i=1;i<=n;i++)
        l[i]=new lista;
    for(i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        elem *p;
        p=new elem;
        p->info=y;
        if(l[x]->u==NULL)
        {
            l[x]->urm=p;
            l[x]->u=p;
        }
        else
        {
            l[x]->u->urm=p;
            l[x]->u=p;
        }
    }
    f.close();
    int a[50001]={0},nr=n-1;
    bool v[50001]={false};
    for(i=1;i<=n;i++)
    {
        if(v[i]==0)
            dfstop(l,i,a,v,nr);
    }
    ofstream g("sortaret.out");
    for(i=0;i<n;i++)
        g<<a[i]<<" ";
    g.close();
    for(i=1;i<=n;i++)
        delete l[i];
    return 0;
}