Cod sursa(job #1705775)

Utilizator RaresvisRares Visalom Mihail Raresvis Data 20 mai 2016 23:17:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

long N, M;
bool visited[50001];

void DFS (const std::vector< std::vector<long> > &adjList, stack<long> &stack, long node) {
	visited[node] = true;

	for (long i = 0; i < adjList[node].size(); i++) {
		if (!visited[adjList[node][i]]) {
			DFS(adjList, stack, adjList[node][i]);
		}
	}

	stack.push(node);
}

int main () {
	FILE* input = fopen("sortaret.in", "r");
	FILE* output = fopen("sortaret.out", "w");

	fscanf(input, "%ld %ld", &N, &M);

	std::vector< std::vector<long> > adjList(N+1, std::vector<long>()); 

	long u, v;
	for (long i = 0; i < M; i++) {
		fscanf(input, "%ld %ld", &u, &v);

		adjList[u].push_back(v);
	}

	stack<long> stack;
	for (long i = 1; i <= N; i++) {
		if (!visited[i]) {
			DFS(adjList, stack, i);
		}
	}	

	long s;
	while (!stack.empty()) {
		s = stack.top();
		stack.pop();

		fprintf(output, "%ld ", s);
	}

	fclose(input);
	fclose(output);

	return 0;
}