Cod sursa(job #1739433)

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

#include <fstream>

using namespace std;

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

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

nod *Adj[101], *ultim[101];
int n, m;
int color[101], pred[101], d[101], f[101], timp, vc[101], 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;
}