Cod sursa(job #2670913)

Utilizator davidcotigacotiga david davidcotiga Data 10 noiembrie 2020 22:16:41
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>

using namespace std;

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

vector<int> G[50005];
int checked[50005];
stack<int> S;

void DFS(int node) {
	int next;
	checked[node] = 1;

	for (int i = 0; i < G[node].size(); ++i) {
		next = G[node][i];

		if (!checked[next])
			DFS(next);

	}
	S.push(node);
}

int main() {
	int N, M;

	fin >> N >> M;

	int x, y;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y;
		G[x].push_back(y);
	}

	for (int i = 1; i <= N; ++i)
		if (!checked[i])
			DFS(i);

	while (!S.empty()) {
		fout << S.top() << " ";
		S.pop();
	}

	return 0;
}