Cod sursa(job #631104)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 6 noiembrie 2011 23:21:51
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <vector>
using namespace std;

short n, m, grad[50100], coada[50100];
vector <int> vecini[50100];

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(vector <int>::iterator it=vecini[x].begin();it!=vecini[x].end();it++)
    {
      --grad[*it];
      if (grad[*it]==0)
        coada[++coada[0]]=*it;
    }
  }
}

void citire()
{
  int 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].push_back(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;
}