Cod sursa(job #2425650)

Utilizator AndreiAsAndrei Sugeac AndreiAs Data 24 mai 2019 22:46:14
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define maxn 50000
#define maxm 100000
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int N, M;
vector <int> lista[maxn];

void topologicSortPlus(int nod, bool viz[], stack <int> &stiva) {
	viz[nod] = true;
	for (int x : lista[nod]) {
		if (viz[x] == false)
			topologicSortPlus(x, viz, stiva);
	}
	stiva.push(nod);
}

void topologicSort() {
	stack <int> stiva;
	bool *viz = new bool[N + 1];
	for (int i = 1; i <= N; ++i) {
		viz[i] = false;
	}
	for (int i = 1; i <= N; ++i) {
		if (viz[i] == false)
			topologicSortPlus(i, viz, stiva);
	}

	while (stiva.empty() == false) {
		g << stiva.top() << " ";
		stiva.pop();
	}
}

int main()
{
	f >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int x, y;
		f >> x >> y;
		lista[x].push_back(y);
	}
	topologicSort();
	return 0;
}