Cod sursa(job #2665961)

Utilizator TheSharkCristian-Andrei Ionescu TheShark Data 31 octombrie 2020 16:02:32
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
#include<stack>
#define NMAX 100001

using namespace std;

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

vector<unsigned int> adjList[NMAX];
bool isVisited[NMAX];

stack<unsigned int> sortedGraph;

void dfs(unsigned int startNode) {
	if (isVisited[startNode]) {
		return;
	}

	isVisited[startNode] = true;
	for (const auto& node : adjList[startNode]) {
		if (!isVisited[node]) {
			dfs(node);
		}
	}

	sortedGraph.push(startNode);
}

void printResult() {
	if (sortedGraph.empty()) {
		return;
	}

	unsigned int x = sortedGraph.top();
	sortedGraph.pop();
	printResult();
	out<<x<<' ';
}

int main() {

	unsigned int N, M, S;

	in >> N >> M >> S;
	for (unsigned int i = 0; i < M; ++i) {
		unsigned int startNode, endNode;
		in >> startNode >> endNode;
		adjList[startNode].push_back(endNode);
	}

	for (unsigned int node = 1; node <= N; ++node) {
		if (!isVisited[node]) {
			dfs(node);
		}
	}

	printResult();

	return 0;
}