Cod sursa(job #1266724)

Utilizator cosgbCosmin cosgb Data 19 noiembrie 2014 00:20:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

void dfs(long node, const vector<vector<long> >& ad, vector<bool>& visited, stack<long>& st)
{
	visited[node] = true;
	int size = ad[node].size();
	for (int i = 0; i < size; i++) {
		if (!visited[ad[node][i]]) {
			dfs(ad[node][i], ad, visited, st);
		}
	}
	st.push(node);
}


int main()
{
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	long n, m, node1, node2;
	scanf("%ld %ld", &n, &m);
	vector<vector<long> > ad(n + 1, vector<long>());
	vector<bool> visited(n + 1, false);
	for (long i = 0; i < m; i++) {
		scanf("%ld %ld", &node1, &node2);
		ad[node1].push_back(node2);
	}

	stack<long> st;
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			dfs(i, ad, visited, st);
		}
	}

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

	printf("\n");

	return 0;
}