Cod sursa(job #1839383)

Utilizator cat_a_stropheTina Elisse Pop cat_a_strophe Data 2 ianuarie 2017 20:50:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#define NMAX 50000
#define MMAX 100000
using namespace std;

bool vizitat[NMAX];
vector<int> result;
vector<int> vecini[NMAX];

void DFS(int source) {
	vizitat[source] = true;
	for (int i = 0; i < vecini[source].size(); ++ i) {
		if (!vizitat[vecini[source][i]]) {
			DFS(vecini[source][i]);
		}
	}
	result.push_back(source);
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	int noduri, muchii;
	scanf("%d%d", &noduri, &muchii);
	
	for (int i = 0; i < muchii; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		vecini[x].push_back(y);
	}

	for (int i = 1; i <= noduri; ++ i) {
		if (!vizitat[i]) {
			DFS(i);
		}
	}

	for (int i = result.size() - 1; i >= 0; -- i) {
		printf("%d ", result[i]);
	} 
	printf("\n");
	return 0;
}