Pagini recente » Cod sursa (job #1229365) | Cod sursa (job #147650) | Cod sursa (job #2714613) | Cod sursa (job #1368449) | Cod sursa (job #2231005)
#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;
}