Cod sursa(job #2424752)

Utilizator dornexDorneanu Eduard-Gabriel dornex Data 23 mai 2019 20:12:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
#include <queue>
#include <list>
using namespace std;

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

void DFS(vector <vector <int>>& G, vector<int>& viz, list <int>& L, int start) {
	viz[start] = 1;
	for (auto x : G[start])
		if (viz[x] == 0) {
			DFS(G, viz, L, x);
		}
	L.push_front(start);
}

int main() {

	int n, m;
	f >> n >> m;

	vector < vector < int >> G(n + 1);
	vector < int > viz(n + 1, 0);
	list <int> L;
	queue <int> Q;

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

	for (int i = 1; i <= n; i++) {
		if(viz[i] == 0)
			DFS(G, viz, L, i);
	}

	for (auto x : L)
		g << x << ' ';

	return 0;
}