Cod sursa(job #2668466)

Utilizator Cibotaru.MateiMatei-Stefan Cibotaru Cibotaru.Matei Data 4 noiembrie 2020 22:17:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
using namespace std;

int dfs(vector<list<int>>& graph, vector<bool>& visited, vector<int>& time, int start, int now) {
	now++;
	for (int i : graph[start]) {
		if (!visited[i]) {
			visited[i] = true;
			now = dfs(graph, visited, time, i, now);
		}
	}
	now++;
	time[start] = now;
	return now;
}

int main()
{
	ifstream fi("sortaret.in");
	ofstream fo("sortaret.out");

	int m, n;
	
	fi >> n >> m;
	vector<list<int>> graph(n);
	
	for (int i = 0; i < m; i++) {
		int a, b;
		fi >> a >> b;
		a--;
		b--;
		graph[a].push_back(b);
	}

	vector<bool> visited(n, false);
	vector<int> time(n);
	int now = 0;

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			now = dfs(graph, visited, time, i, now);
		}
	}

	vector<pair<int, int>> topol;
	for (int i = 0; i < n; i++) {
		topol.push_back(pair<int, int>(i, time[i]));
	}
	
	sort(topol.begin(), topol.end(), [](pair<int, int> a, pair<int, int> b) { return a.second > b.second; });

	for (auto& i : topol) {
		fo << i.first + 1 << " ";
	}

	fi.close();
	fo.close();
	return 0;
}