Cod sursa(job #1194742)

Utilizator c0rn1Goran Cornel c0rn1 Data 4 iunie 2014 18:43:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define add push_back

using namespace std;
vector<int> v[50005];
int sol[50005];
int n, m;
int grad[50005];

void Citire()
{
   int i, x, y;
   scanf("%d %d", &n, &m);
   for (i=0; i<m; i++)
   {
      scanf("%d %d", &x, &y);
      if (x!=y)
      {
         v[x].add(y);
         grad[y]++;
      }
   }
}

void Sortare()
{
   int i, x, poz=0, p, u=0;
   for (i=1; i<=n; i++)
      if (!grad[i])
         sol[++u]=i;
   for (p=1; p<=u; p++)
   {
      x=sol[p];
      for (vector<int>::iterator it=v[x].begin(); it!=v[x].end(); it++)
         if (grad[*it])
         {
            grad[*it]--;
            if (!grad[*it])
               sol[++u]=*it;
         }
   }
}

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

int main()
{
   freopen("sortaret.in", "r", stdin);
   freopen("sortaret.out", "w", stdout);
   Citire();
   Sortare();
   Afisare();
   return 0;
}