Cod sursa(job #1739394)

Utilizator castle2145Popa Catalin castle2145 Data 9 august 2016 13:31:09
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
//culori: 1 alb, 2 gri, 3 negru

#include <fstream>
#include <iostream>

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

struct nod
{
    int info;
    nod * urm;
};

nod *Adj[50001], *ultimul[50001];
int n, m;
int color[50001], pred[50001], d[50001], f[50001], time;

nod *ultim;

nod *sorted;

void afisare_lista (nod *q)
{
    while(q!=NULL)
    {
        fout<<q->info<<' ';
        q=q->urm;
    }
}

void adaugare (int x, nod *&prim, nod *&ultim)
{
    nod *p;

    p=new nod;
    p->info=x;
    p->urm=NULL;

    if(prim==NULL)
        prim=ultim=p;
    else
    {
        ultim->urm=p;
        ultim=p;
    }
}

void creare ()
{
    int x, i, y;
    fin>>n>>m;

    for(i=1;i<=n;i++)
        ultimul[i]=NULL;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        adaugare(y, Adj[x], ultimul[x]);
    }
}

void DFS_VISIT (int u)
{
    color[u]=2; //White vertex u has just been discovered
    time=time+1;
    d[u]=time;

    int v;
    nod *p;
    p=new nod;
    p=Adj[u];
    while(p!=NULL)
    {
        v=p->info; //Explore edge (u,v).
        if(color[v]==1)
        {
            pred[v]=u;
            DFS_VISIT(v);
        }
        p=p->urm;
    }

    color[u]=3; //Blacken u; it is finished.

    fout<<u<<' ';

    time=time+1;
    f[u]=time;
}

void DFS ()
{
    int u;
    for(u=1;u<=n;u++)
    {
        color[u]=1;
        pred[u]=-1;
    }

    time=0;

    for(u=1;u<=n;u++)
        if(color[u]==1)
            DFS_VISIT(u);
}

void topological_sort ()
{
    DFS ();
}

int main()
{
    creare();
    topological_sort();
    return 0;
}