Cod sursa(job #2192092)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 4 aprilie 2018 17:01:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#define maxn 50000

using namespace std;

vector <int> v[maxn+5];
int sz[maxn+5];
int grad[maxn+5];

int qu[maxn+5]; /// coada in care introduc nodurile de grad 0

int main ()
{
  ifstream fin ( "sortaret.in" );
  ofstream fout ( "sortaret.out" );

  int n, m; /// varfuri muchii

  fin >> n >> m;

  int i, a, b;

  for ( i = 0; i < m; i++ )
  {
    fin >> a >> b;
    a--; b--;
    v[a].push_back ( b );
    sz[a]++;
    grad[b]++;
  }

  int st = 0, dr = -1;
  for ( i = 0; i < n; i++ )
    if ( grad[i] == 0 )
      qu[++dr] = i;

  int nod, nn;

  while ( st <= dr )
  {
    nod = qu[st];
    fout << nod + 1 << ' ';
    for ( i = 0; i < sz[nod]; i++ )
    {
      nn = v[nod][i];
      grad[nn]--;
      if ( grad[nn] == 0 )
        qu[++dr] = nn;
    }
    st++;
  }

  fin.close ();
  fout.close ();

  return 0;
}