Cod sursa(job #3224946)

Utilizator Radu_VasileRadu Vasile Radu_Vasile Data 16 aprilie 2024 16:44:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
#define MAXN 50000
using namespace std;
vector <int> v[MAXN + 1];
bitset <MAXN + 1> frecv;
int ns, s[MAXN + 1];
void dfs(int node){
  frecv[node] = 1;
  for(auto &i : v[node])
    if(frecv[i] == 0)
      dfs(i);
  s[++ns] = node;
}
int main(){
  FILE *fin, *fout;
  int n, i, y, x, m;
  fin = fopen( "sortaret.in", "r" );

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

  for( i = 1; i <= n; i++ )
    if(frecv[i] == 0)
      dfs(i);

  fclose( fin );
  fout = fopen( "sortaret.out", "w" );

  while( ns > 0 ){
    fprintf(fout, "%d ", s[ns--]);
  }

  fclose( fout );
  return 0;
}