Cod sursa(job #1739437)

Utilizator castle2145Popa Catalin castle2145 Data 9 august 2016 14:40:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
//culori: 1 alb, 2 gri, 3 negru

#include <fstream>
#define NMAX 50001

using namespace std;

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

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

nod *Adj[NMAX], *ultim[NMAX];
int n, m;
int color[NMAX], pred[NMAX], d[NMAX], f[NMAX], timp, vc[NMAX], k;

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++)
        ultim[i]=NULL;

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

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

    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.

    vc[++k]=u;

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

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

int main()
{
    creare();
    DFS();
    for(int i=k;i>=1;i--)
        fout<<vc[i]<<' ';
    return 0;
}