Cod sursa(job #1704143)

Utilizator andreibotilaBotila Andrei andreibotila Data 18 mai 2016 10:02:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <stdio.h>
#include <deque>
#include <stack>
#include <vector>
#include <stdlib.h>
#include <set>

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

	int N, M;
	fscanf(in, "%d %d", &N, &M);
	
	std::vector<int> graf[N];

	for (int i = 0; i < M; i++) {
		int nod1, nod2;
		fscanf(in, "%d %d", &nod1, &nod2);
		graf[nod1 - 1].push_back(nod2 - 1);
	}

	std::stack<std::pair<bool, int> > dfStack;
	std::vector<int> visited;
	std::deque<int> endOrder;
	std::set<int> setul;

	for (int i = 0; i < N; i++) {
		visited.push_back(0);
	}

	for (int i = 0; i < N; i++) {
		if (visited[i] == 0) {
			dfStack.push(std::make_pair(false, i));
			
			while (!dfStack.empty()) {
				std::pair<bool, int> nod = dfStack.top();
				dfStack.pop();

				if (nod.first) {
					if (setul.insert(nod.second).second) {
						endOrder.push_front(nod.second);
					}
					continue;
				}

				dfStack.push(std::make_pair(true, nod.second));
				visited[nod.second] = 1;
				for (unsigned int i = 0; i < graf[nod.second].size(); i++) {
					if (visited[graf[nod.second][i]] == 0) {
						dfStack.push(std::make_pair(false, graf[nod.second][i]));
					}
				}
			}
		}
	}

	for (unsigned int i = 0; i < endOrder.size(); i++) {
		fprintf(out, "%d ", endOrder[i] + 1);
	}

	fclose(in);
	fclose(out);
	return 0;
}