SORTAREA TOPOLOGICA

SORTAREA TOPOLOGICA

Se da un graf orientat. Orientarea muchiilor corespunde unei relatii de ordine de la nodul sursa catre cel destinatie. Ni se cere sa asezam nodurile in asa fel incat pentru orice muchie (u,v), u sa apara inaintea lui v. Aceasta operatie se numeste sortare topologica.

Sortarea topologica are sens numai daca este aplicata asupra unui graf orientat si aciclic. De ce? Daca nu ar fi graf orientat, nu am avea despre ce ordine sa discutam. Iar un ciclu ar fi indeajuns pentru a nu putea stabili o ordine intre nodurile care il alcatuiesc. Un graf orientat este aciclic daca si numai daca explorarea lui in adancime nu contine arce de revenire.

Sa consideram urmatorul exemplu:

Fig. 3.1

Ei bine, de aici si pana la a obtine o succesiune de noduri ordonate nu este decat un singur pas: avem grija sa asezam nodul radacina al fiecarui subarbore intr-o stiva, iar pentru afisare scoatem pe rand cate un nod din stiva tiparind odata cu el si nodurile din arbore sau in ordinea obtinuta.

Fig 3.2

Pentru un graf dat pot exista mai multe insiruiri de noduri care sa respecte cerinta.

O varianta a problemei anterioare este descrisa in formularea urmatoare:

O sortare topologica a varfurilor unui graf orientat aciclic este o operatie de ordonare liniara a varfurilor, astfel incat, daca exista un arc ( i j ), atunci i apare inaintea lui j in aceasta ordonare.

Algoritm pentru sortarea topologica

Date de intrare

In fisierul de intrare sortaret.in vom avea pe prima linie doua numere intregi N si M. Pe fiecare dintre urmatoarele M linii se vor afla cate doua numere intregi, separate intre ele printr-un spatiu, X si Y, cu semnificatia ca exista arc de la nodul X catre nodul Y

Date de iesire

Fisierul de iesire sortaret.out va contine pe o singura linie N numere separate intre ele prin spatii, care reprezinta sortarea topologica a nodurilor grafului dat. Daca exista mai multe solutii se va afisa oricare.

Restrictii

1 ≤ N ≤ 50000

1 ≤ M ≤ 100000

Pot exista mai multe arce intre doua noduri X si Y

Exemplu

Fig. 3.3

#include <fstream>

#include <stack>

using namespace std;

#define NUME 'sortaret'

ifstream fi(NUME'.in');

ofstream fo(NUME'.out');

#define MAXN 50001

int N, M, gradin[MAXN];

int Used[MAXN];

stack<int> C;

struct item *L[MAXN];

void df(int s)

C.push(s);

inline void add(int a, int b) ;

L[a] = p;

gradin[b] ++;

int main()

for (int i = 1; i <= N; ++i)

if (gradin[i] == 0)

df(i);

while (!C.empty())

return 0;