Cod sursa(job #2231005)

Utilizator gabriel-mocioacaGabriel Mocioaca gabriel-mocioaca Data 12 august 2018 16:56:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <fstream>

#define cin in
#define cout out

using namespace std;

bool not_dag = false;

void ts(int x, vector<list<int>> &graph, vector<int> &vis, stack<int> &top_sort) {
	if (not_dag)
		return;

	if (vis[x] == 1)
		not_dag = true;

	if (vis[x] == 2) 
		return;

	vis[x] = 1;

	for (auto it : graph[x]) {
		ts(it, graph, vis, top_sort);
	}

	vis[x] = 2;
	top_sort.push(x);
}

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

	int n, m, i, x, y;
	
	cin >> n >> m;
	
	vector<list<int>> graph(n + 1);
	vector<int> vis(n + 1, 0);
	stack<int> top_sort;

	for (i = 1; i <= m; ++i) {
		cin >> x >> y;
		graph[x].push_back(y);
	}

	for (i = 1; i <= n; ++i) {
		if (vis[i] == 0) {
			ts(i, graph, vis, top_sort);
		}
	}

	if (not_dag) {
		cout << "Imposible";
	}
	else {
		while (!top_sort.empty()) {
			cout << top_sort.top() << ' ';
			top_sort.pop();
		}
	}
	return 0;
}