Cod sursa(job #1592949)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 8 februarie 2016 10:37:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>         /* sortarea topologica: un graf orientat fara cicluri se poate sorta topologic -
#include <stdlib.h>           numarul de ordine al fiecarui nod trebuie sa fie mai mare decat numerele de
                              ordine ale parintilor(daca muchia (u,v) apartine grafului u trebuie sa apara
                              in sortare inaintea lui v */

#define NMAX 50005
int n, m, t;

int viz[NMAX];

struct node {
	int inf;
        struct node *pnext;
}*v[NMAX];

struct node *h;                                                   /*  *h este variabila globala */


void push(int x) {

 	struct node *p;

        p = new node;
        p->inf = x;
        p->pnext = h;
        h = p;
}
node* inserare_inceput(node* p,int x){
    node* elem=new node;
    elem->inf=x;
    elem->pnext=p;
    return elem;
}
void DFS(int x){
    if(viz[x]==0){
        viz[x]=++t;
        node *parcurg=v[x];
        while(parcurg){
            DFS(parcurg->inf);
            parcurg=parcurg->pnext;
        }
        push(x);
    }
}

int main() {
  freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);
  int i, j, k;
  struct node *pc;

  scanf("%d", &n);
  scanf("%d", &m);

  for (k = m; k >= 1; k--) {
     scanf("%d%d", &i, &j);
     v[i]=inserare_inceput(v[i],j);
  }

  h = NULL;



  t = 1;
  for (i = 1; i <= n; i++) {
    if (viz[i] == 0) {
      DFS(i);
    }
  }

  pc = h;
  while (pc != NULL) {
    printf("%d ", pc->inf);
    pc = pc->pnext;
  }
  printf("\n");
  return 0;

}