Cod sursa(job #1656295)

Utilizator radu.bRadu Brumariu radu.b Data 19 martie 2016 04:26:40
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>
#include<stdlib.h>

#define NMax 50001
#define ALB 0
#define GRI 1
#define NEGRU 2

int D[NMax][NMax] = {{0}};
int R[NMax] = {0};
int visited[NMax] = {0};
int idx;

int visit(int n);
void print_matrix(int n) {
  for(int i = 1; i < n; i++) {
    for(int j = 1; j < n; j++) {
      printf("%d ", D[i][j]);
    }
    printf("\n");
  }
}
int main(void) {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w+", stdout);

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

  for(int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    D[x][y] = 1;
  }

  for(int i = 1; i <= n; i++) {
    visit(i);
  }

  for(int i = idx; i; i--) {
    printf("%d ", R[i]);
  }
  printf("\n");

  return 0;
}

int visit(int n) {
  if(visited[n] == NEGRU) return 0;
  if(visited[n] == GRI) {
    printf("**** cycle detected **** \n");
    return -1;
  }
  visited[n] = GRI;
  for(int i = 1; i <= n; i++) {
    if(D[n][i] == 1) {
      if(visited[i] == ALB)
        visit(i);
    }
  }
  visited[n] = NEGRU;
  R[++idx] = n;
  return 0;
}