Cod sursa(job #3237521)

Utilizator tsg38Tsg Tsg tsg38 Data 9 iulie 2024 19:15:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 50001;

vector<int> G[DIM];
int deg[DIM];

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, m, u, v;

  fin >> n >> m;
  while ( m-- ) {
	fin >> u >> v;
	G[u].push_back(v);
    ++deg[v];
  }
  queue<int> q;
  for ( int i = 1; i <= n; ++i ) {
	if ( deg[i] == 0 ) q.push(i);
  }
  while ( !q.empty() ) {
	u = q.front();
	q.pop();
	for ( auto v : G[u] ) {
	  --deg[v];
	  if ( deg[v] == 0 ) {
		q.push(v);
	  }
	}
	fout << u << " ";
  }
  fin.close();
  fout.close();
  return 0;
}