Pagini recente » Cod sursa (job #2621735) | Cod sursa (job #1319283) | Cod sursa (job #1273393) | Cod sursa (job #2599860) | Cod sursa (job #3196907)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
std::vector<std::vector<int> > listaAdiacenta;
std::vector<bool> vizitat;
std::stack<int> stiva;
std::vector<int> sortareTopologica;
// parcurgere in adancime
void DFS(int s) {
stiva.push(s); // inseram nodul sursa in stiva vida
vizitat[s] = true; // marcam nodul sursa ca vizitat
while (!stiva.empty()) { // cat timp stiva nu este vida
int nod = stiva.top();
bool nevizitat = false; // presupunem ca nu mai avem vecini nevizitati
for (int vecin : listaAdiacenta[nod]) { // parcurgem vecinii nodului
if (!vizitat[vecin]) {
stiva.push(vecin); // inseram vecinul in stiva
vizitat[vecin] = true; // marcam vecinul ca vizitat
nevizitat = true; // avem vecini nevizitati
}
}
if (!nevizitat) { // daca nu mai avem vecini nevizitati, scoatem nodul din stiva
stiva.pop();
sortareTopologica.push_back(nod);
}
}
}
int main(){
std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
int N, M;
fin >> N >> M;
listaAdiacenta.assign(N, std::vector<int>());
vizitat.assign(N, false);
sortareTopologica.clear();
// construire DAG
for(int i = 0; i < M; i++){
int x, y;
fin >> x >> y;
x--;
y--;
listaAdiacenta[x].push_back(y);
}
// parcurgere DFS
for(int i = 0; i < N; i++)
if(!vizitat[i])
DFS(i);
// afisare sortare topologica
for(int i = N - 1; i >= 0; i--) // afisam sortarea topologica in ordine inversa
fout << sortareTopologica[i] + 1 << " ";
return 0;
}