Cod sursa(job #2533937)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 29 ianuarie 2020 21:14:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

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

int const maxim = 50005;

vector<int> stocare[maxim];
vector<bool> visited;
vector<int> ans;
int n, m;

void citire() {
	in >> n >> m;
	int a, b;
	for (int i = 1; i <= m; i++) {
		in >> a >> b;
		stocare[a].push_back(b);
	}
}

void dfs(int v) {
	visited[v] = true;
	for (size_t i = 0; i < stocare[v].size(); i++) {
		if (visited[stocare[v][i]] == false) dfs(stocare[v][i]);
	}
	ans.push_back(v);
}

void topological() {
	visited.assign(n+1, false);
	ans.clear();
	for (int i = 1; i <= n; i++) {
		if (!visited[i])dfs(i);
	}
	reverse(ans.begin(), ans.end());
}

void afisare() {
	for (int i = 0; i < ans.size(); i++) {
		out << ans[i] << " ";
	}
}


int main() {
	citire();
	topological();
	afisare();
	return 0;
}