Cod sursa(job #1176338)

Utilizator cosgbCosmin cosgb Data 25 aprilie 2014 22:50:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

void dfs(vector<vector<long> > &lista_ad, vector<bool> &visited, int node_id, stack<long> &stiva) {
	visited[node_id] = true;
	for (int i = 0; i < lista_ad[node_id].size(); i++) {
		if (!visited[lista_ad[node_id][i]]) {
			dfs(lista_ad, visited, lista_ad[node_id][i], stiva);
		}
	}

	stiva.push(node_id);
}


int main()
{
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	long M, N, id1, id2;

	scanf("%ld%ld", &N, &M);

	vector<vector<long> > lista_ad(N + 1, vector<long>(0, 0));
	vector<bool> visited(N + 1, false);
	stack<long>stiva;

	for (int i = 0; i < M; i++) {
		scanf("%ld%ld", &id1, &id2);
		lista_ad[id1].push_back(id2);
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i] == false) {
			dfs(lista_ad, visited, i, stiva);
		}
	}

	while (!stiva.empty()) {
		printf("%ld ", stiva.top());
		stiva.pop();
	}


	return 0;
}