Cod sursa(job #2796920)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 9 noiembrie 2021 00:15:54
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
// Mihai Priboi

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 100000

struct point {
  vector<int> muchii;
  int depth;
} noduri[MAXN + 1];

int v[MAXN + 1];

void fill( int nod ) {
  int i;
  noduri[nod].depth = 1;
  for( i = 0; i < noduri[nod].muchii.size(); i++ ) {
    if( !noduri[noduri[nod].muchii[i]].depth )
      fill( noduri[nod].muchii[i] );
    noduri[nod].depth += noduri[noduri[nod].muchii[i]].depth;
  }
}

bool cmp( int a, int b ) {
  return noduri[a].depth > noduri[b].depth;
}

int main() {
  FILE *fin, *fout;
  int n, m, i, x, y, cnt;

  fin = fopen( "sortaret.in", "r" );

  fscanf( fin, "%d%d", &n, &m );
  for( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d", &x, &y );
    noduri[x].muchii.push_back(y);
  }

  fclose( fin );

  cnt = 0;
  for( i = 1; i <= n; i++ ) {
    if( !noduri[i].depth )
      fill(i);
    v[i - 1] = i;
  }

  sort( v, v + n, cmp );

  fout = fopen( "sortaret.out", "w" );
  
  for( i = 0; i < n; i++ )
    fprintf( fout, "%d ", v[i] );

  fclose( fout );
  return 0;
}