Cod sursa(job #483509)

Utilizator Smaug-Andrei C. Smaug- Data 8 septembrie 2010 23:15:11
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <string>

#define MAXN 50010

struct node {
  node *next;
  int dest;
};

int main(){

  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);

  int N, M, i, j, k, v[MAXN], Q[MAXN], Qi = 1;
  node *g[MAXN], *aux;

  memset(v, 0, sizeof(v));

  scanf("%d%d", &N, &M);
  for(i = 1; i <= N; i++){
    aux = new node;
    scanf("%d%d", &j, &k);
    aux->dest = k;
    aux->next = g[j];
    g[j] = aux;
    v[k]++;
  }

  for(i = 1; i <= N; i++)
    if(v[i] == 0)
      Q[Qi++] = i;

  for(i = 1; i <= Qi; i++){
    aux = g[Q[i]];
    while(aux != NULL){
      if(--v[aux->dest] == 0)
	Q[Qi++] = aux->dest;
      aux = aux->next;
    }
  }

  for(i = 1; i <= N; i++)
    printf("%d ", Q[i]);

  return 0;

}