Cod sursa(job #1687477)

Utilizator mist.moonDenisa Gherghel mist.moon Data 12 aprilie 2016 21:26:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <deque>
using namespace std;
const int MAXN = 50003;

vector<int> G[MAXN];
vector<bool> vizitat(MAXN,false);
deque<int> sortat;
int n, m;

void citire() {
	int a, b;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		cin >> a >> b;
		G[a].push_back(b);
	}
}

void dfs(int node) {
	vizitat[node] = true;

	for (int i = 0;i < G[node].size();i++) {
		if (!vizitat[G[node][i]]) dfs(G[node][i]);
	}

	sortat.push_back(node);

}

void sortareTopologica() {
	for (int i = 1;i <= n;i++) {
		if (!vizitat[i]) {
			dfs(i);
		}
	}
}

void afisare() {
	while (!sortat.empty()) {
		cout << sortat.back() << " ";
		sortat.pop_back();
	}
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	citire();
	sortareTopologica();
	afisare();

	return 0;
}