Pagini recente » Cod sursa (job #956085) | Cod sursa (job #2719795) | Cod sursa (job #1971871) | Cod sursa (job #1262776) | Cod sursa (job #3166541)
#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 &vizitatPermanent, vi &vizitatTemporar, vi &lista, int nod) {
vizitatPermanent[nod] = vizitatTemporar[nod] = 1;
bool ans = true;
for(auto &vecin : graf[nod]) {
if(!vizitatPermanent[vecin]) {
ans = dfs(graf, vizitatPermanent, vizitatTemporar, lista, vecin);
}
else if(vizitatTemporar[vecin])
return false;
if(!ans)
return false;
}
vizitatTemporar[nod] = 0;
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 vizitatPermanent(n), vizitatTemporar(n);
for(int i = 0; i < m; i++) {
int a, b;
fin >> a >> b;
--a;
--b;
graf[a].emplace_back(b);
}
bool ans = true;
vi lista;
for(int nod = 0; ans && nod < n; nod++)
if(!vizitatPermanent[nod])
ans = dfs(graf, vizitatPermanent, vizitatTemporar, lista, nod);
if(!ans)
fout << "IMPOSSIBLE";
else {
reverse(lista.begin(), lista.end());
for(auto &nod : lista)
fout << nod + 1 << " ";
}
fin.close();
fout.close();
return 0;
}