Cod sursa(job #151087)

Utilizator AlxCojocaru Alexandru Alx Data 7 martie 2008 19:59:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>
#include <vector.h>
using namespace std;
long n,m,x,y,deg[50001],q[50001],nq=0;
vector<long> a[50001];
int main()
{
 freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
 scanf("%ld %ld\n",&n,&m);
 long i;
 for (i=0;i<m;i++)
 {
  scanf("%ld %ld\n",&x,&y);
  a[x].push_back(y);
  deg[y]++;
 }
 for (i=1;i<=n;i++)
  if (deg[i]==0)
   q[nq++]=i;
 long poz=0;
 while (poz<nq)
 {
  for (i=0;i<a[q[poz]].size();i++)
  {
   deg[a[q[poz]][i]]--;
   if (deg[a[q[poz]][i]]==0)
    q[nq++]=a[q[poz]][i];
  }
  poz++;
 }
 for (i=0;i<n;i++)
  printf("%ld ",q[i]);
 return 0;
}