Pagini recente » Cod sursa (job #1306154) | Cod sursa (job #3269148) | Cod sursa (job #1950865) | Cod sursa (job #1707586) | Cod sursa (job #3166536)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
bool dfs(vvi &graf, vi &vizitat, vi &ordine, vi &lista, int nod, int nrVizitat, int currOrdine) {
vizitat[nod] = nrVizitat;
ordine[nod] = currOrdine;
bool ans = true;
for(auto &vecin : graf[nod]) {
if(!vizitat[vecin])
ans = dfs(graf, vizitat, ordine, lista, vecin, nrVizitat, currOrdine + 1);
else if(vizitat[nod] == vizitat[vecin] && ordine[nod] > ordine[vecin])
return false;
if(!ans)
return false;
}
lista.emplace_back(nod);
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
fin >> n >> m;
vvi graf(n, vi());
vi vizitat(n), ordine(n);
for(int i = 0; i < m; i++) {
int a, b;
fin >> a >> b;
--a;
--b;
graf[a].emplace_back(b);
}
bool ans = true;
int nrVizitat = 1;
vi lista;
for(int nod = 0; ans && nod < n; nod++)
if(!vizitat[nod])
ans = dfs(graf, vizitat, ordine, lista, nod, nrVizitat++, 1);
if(!ans)
fout << "IMPOSSIBLE";
else {
reverse(lista.begin(), lista.end());
for(auto &nod : lista)
fout << nod + 1 << " ";
}
fin.close();
fout.close();
return 0;
}