Cod sursa(job #1762362)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 23 septembrie 2016 14:44:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
#include<vector>

using namespace std;

int n, m, x, y;
vector<vector<int> > adiacente(50001);
vector<bool> vizitat(50001);
vector<int> sol;

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

	for (int i = 0; i < adiacente[nod].size(); i ++)
		if (!vizitat[adiacente[nod][i]])
			dfs(adiacente[nod][i]);
	sol.push_back(nod);
}

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

	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i ++) {
		scanf("%d %d", &x, &y);
		adiacente[x].push_back(y);
	}

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

	for (int i = sol.size() - 1; i >= 0; i --)
		printf("%d ", sol[i]);

	return 0;
}