Cod sursa(job #2294828)

Utilizator andreiulianAndrei andreiulian Data 2 decembrie 2018 20:50:11
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
bool viz[50005];
int gi[50005];
vector<int> v[50005];
vector<int> sol;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
void dfs(int i);

int main() {
	int n, m, a, b;
	in >> n >> m;
	for (int i = 1; i <= m; ++i) {
		in >> a >> b;
		v[a].push_back(b);
		//v[b].push_back(a);
		gi[b]++;
	}
	for (int i = 1; i <= n; ++i) {
		if (gi[i] == 0 && !viz[i]) {
			dfs(i);
		}
	}
	for (auto it = sol.rbegin(); it != sol.rend(); ++it) {
		cout << *it << ' ';
	}
}

void dfs(int i) {
	viz[i] = 1;
	for (auto it = v[i].begin(); it != v[i].end(); ++it) {
		if (!viz[*it]) {
			dfs(*it);
		}
	}
	sol.push_back(i);
}