Cod sursa(job #2819677)

Utilizator lolismekAlex Jerpelea lolismek Data 18 decembrie 2021 20:07:07
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <deque>

#define pb push_back
#define pf push_front
#define popf pop_front

using namespace std;

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

const int N = 5 * 1e4 + 1;
vector <int> adj[N];
vector <int> viz(N + 1, 0);
stack <int> stiva;
deque <int> rasp;

void dfs(int nod) {
	viz[nod] = 1;
	stiva.push(nod);
	for (auto vec : adj[nod]) 
		if (!viz[vec]) 
			dfs(vec);
}

int main() {
	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++){
		int a, b;
		fin >> a >> b;
		adj[a].pb(b);
	}
	for (int i = 1; i <= n; i++) {
		if (!viz[i]) dfs(i);
		while (!stiva.empty()) {
			int x = stiva.top();
			rasp.pf(x);
			stiva.pop();
		}
	}
	while (!rasp.empty()) {
		fout << rasp.front() << " ";
		rasp.popf();
	}
	return 0;
}