Cod sursa(job #631102)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 6 noiembrie 2011 23:01:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>

using namespace std;

short n, m, grad[50100], coada[50100], vecini[50100][500];


void rezolvare()
{
  int x;
  coada[0]=0;
  for (x=1;x<=n;x++)
    if (grad[x]==0)
      coada[++coada[0]]=x;
  for(int i=1;i<=n;i++)
  {
    x=coada[i];
    for(int j=1;j<=vecini[x][0];j++)
    {
      --grad[vecini[x][j]];
      if (grad[vecini[x][j]]==0)
        coada[++coada[0]]=vecini[x][j];
    }
  }
}

void citire()
{
  short a,b;
//  cout<<"n,m\n";
  scanf("%d %d",&n,&m);
  for (int i=1;i<=5000;i++)
  {  
    vecini[i][0]=0;
    grad[i]=0;
  }
  for (int i=1;i<=m;i++)
  {
//  cout<<"a,b="<<"\n";
    scanf("%d %d", &a, &b);
    vecini[a][++vecini[a][0]]=b;
    grad[b]++;
  }
}

void afisare()
{
  for(int i=1;i<=n;i++)
    printf("%d ",coada[i]);
}

int main()
{
  freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);  
  citire();
  rezolvare();
  afisare();
  return 0;
}