Cod sursa(job #2214749)

Utilizator bcrsqCont Sters bcrsq Data 19 iunie 2018 23:47:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 50000

void dfs(int node);

vector<int> topsort;
vector<int> adj[NMAX + 1];
int visited[NMAX + 1];

int main () {
	int n, m;

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

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

	for (int i = 0; i < m; i++) {
		int v1, v2;
		scanf("%d %d", &v1, &v2);

		adj[v1].push_back(v2);
	}

	for (int i = 1; i <= n; i++) {
		if (visited[i] == 0) {
			dfs(i);
		}
	}

	reverse(topsort.begin(), topsort.end());

	for (auto node : topsort) {
		printf("%d ", node);
	}

	printf("\n");

	return 0;
}

void dfs(int node) {
	visited[node] = 1;

	for (auto vecin : adj[node]) {
		if (visited[vecin] == 0) {
			dfs(vecin);
		}
	}

	topsort.push_back(node);
}