Cod sursa(job #1592932)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 8 februarie 2016 10:25:47
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.63 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 5005
int n, m, t;
int x[NMAX][NMAX];
int viz1[NMAX], viz2[NMAX];

struct node {
	int inf;
        struct node *pnext;
};

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


void push(int x) {

 	struct node *p;

        p = (struct node*) malloc(sizeof(struct node));
        p->inf = x;
        p->pnext = h;
        h = p;
}


void df(int u) {

   int v;

   if (viz1[u] == 0) {

     viz1[u] = t;
     t++;
     for (v = 1; v <= n; v++)
        if (x[u][v] == 1) df(v);
     viz2[u] = t;
     push(u);
     t++;
   }
}

void 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 (i = 0; i <= n; i++) {
     for (j = 0; j <= n; j++) {
       x[i][j] = 0;
     }
   }

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

  h = NULL;

  for (i = 0; i <= n; i++) {
    viz1[i] = 0;
    viz2[i] = 0;
  }

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

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


}