Cod sursa(job #2605236)

Utilizator razvan1403razvan razvan1403 Data 24 aprilie 2020 17:22:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#include <vector>
#define dimension 50005
#define ALB 0
#define GRI 1
#define NEGRU 2

using namespace std;

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

typedef struct nod{
    int varf;;
    nod *next;
}*PNOD,NOD;

PNOD L[dimension];
PNOD adresa;
int color[dimension];
int n,m;

void Add(int x,int y)
{
    PNOD p = new NOD;
    p->varf = y;
    p->next = L[x];
    L[x] = p;
}

void read(int &n,int &m)
{
    fin>>n>>m;
    int x,y;
    for(;m>0;m--)
    {
        fin>>x>>y;
        Add(x,y);
    }
}
void Push(int x)
{
    PNOD p = new NOD;
    p->varf = x;
    p->next = adresa;
    adresa = p;
}

void Display()
{
        for(PNOD p = adresa;p;p=p->next)
            fout<<p->varf<<" ";
}

void df(int x)
{
    color[x] = GRI;
    for(PNOD p = L[x];p;p=p->next)
    {
        if(color[p->varf] == ALB)
            df(p->varf);
    }
    color[x] = NEGRU;
    Push(x);
}

void Sortare_Topologica()
{
    int i;
    for(i=1;i<=n;i++)
        if(color[i]==ALB)
            df(i);
}

int main()
{
    read(n,m);
    Sortare_Topologica();
    Display();
    fin.close();
    fout.close();
    return 0;
}