Cod sursa(job #1194755)

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

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

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);
   }
}

void Sortare(int x)
{
   if (v[x].size()==0)
   {
      sol[++sol[0]]=x;
      viz[x]=1;
      return;
   }
   for (vector<int>::iterator it=v[x].begin(); it!=v[x].end(); it++)
      if (!viz[*it])
      {
         viz[*it]=1;
         Sortare(*it);
      }
   sol[++sol[0]]=x;
   viz[x]=1;
}

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

int main()
{
   freopen("sortaret.in", "r", stdin);
   freopen("sortaret.out", "w", stdout);
   int i;
   Citire();
   for (i=1; i<=n; i++)
      if (!viz[i])
         Sortare(i);
   Afisare();
   return 0;
}