Cod sursa(job #2890700)

Utilizator tiut_cristianTiut Cristian tiut_cristian Data 16 aprilie 2022 12:58:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

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

PNOD L[50001], adresa;
int v[50001];
int N, M;

void adaugare(int i, int j)
{
     PNOD p = new NOD;
     p->vf = j;
     p->next = L[i];
     L[i] = p;
}

void citire()
{
     fin >> N >> M;
     int X, Y;
     for(int i = 1; i <= M; i++)
         fin >> X >> Y, adaugare(X,Y);
}

void Push(int nod)
{
     PNOD p = new NOD;
     p->vf = nod;
     p->next = adresa;
     adresa = p;
}

void DF(int nod)
{
    v[nod] = 1;
    PNOD p = L[nod];
    while (p)
    {
        if ( v[p->vf] == 0 )
            DF( p->vf );
        p = p->next;
    }
    v[nod] = 2;
    Push(nod);
}

void sortare()
{
     for (int i = 1; i <= N; i++)
         if (v[i] == 0)
            DF(i);
}

void afisare()
{
     PNOD p = adresa;
     while (p)
         fout << p->vf << ' ', p = p->next ;
}

int main()
{
    citire();
    sortare();
    afisare();

    return 0;
}