Cod sursa(job #2401197)

Utilizator gabriel.crosmanCrosman Gabriel gabriel.crosman Data 9 aprilie 2019 14:58:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int kNmax = 100005;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	vector<int> adj[kNmax];

	void read_input() {
		ifstream fin("sortaret.in");
		fin >> n >> m;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
		}
		fin.close();
	}

	void dfs (int node, queue<int> &q, vector<int> &visited) {

		visited[node] = 1;

		for (int i : adj[node]) {

			if (visited[i] == 0) {
				dfs(i, q, visited);
			}
		}

		q.push(node);
	}

	vector<int> get_result() {

		vector<int> topsort(n);
		vector<int> visited(n + 1);
		queue<int> q;
		int i;
		int j = n - 1;

		for (i = n; i > 0; i--) {
			if (visited[i] == 0) {
				dfs(i, q, visited);
			}

			while (!q.empty()) {
				topsort[j] = q.front();
				q.pop();
				j--;
			}
		}

		return topsort;
	}

	void print_output(vector<int> result) {
		ofstream fout("sortaret.out");
		for (int i = 0; i < int(result.size()); i++) {
			fout << result[i] << ' ';
		}
		fout << '\n';
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}