Pagini recente » Cod sursa (job #1468123) | Cod sursa (job #2551528) | Cod sursa (job #2795122) | Cod sursa (job #1834759) | Cod sursa (job #2792244)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
const int NMAX = 50001;
ifstream fin("sortaret.in");
ofstream fout ("sortaret.out");
class graf{
private:
int nrNoduri, nrMuchii;
vector<int> listaAd[NMAX];
bitset<NMAX> viz;
stack<int> noduriSortTop;
void dfsSortTop(const int &nod);
public:
graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
void adaugaInListaAd(const int &nod1, const int &nod2);
void sortareTopologica();
};
void graf::adaugaInListaAd(const int &nod1, const int &nod2) {
listaAd[nod1].push_back(nod2);
}
void graf::dfsSortTop(const int &nod) {
viz[nod] = true;
for(int i = 0; i < listaAd[nod].size(); i++){
if(!viz[listaAd[nod][i]]){
dfsSortTop(listaAd[nod][i]);
}
}
noduriSortTop.push(nod);
}
void graf::sortareTopologica() {
for(int i = 1; i <= nrNoduri; i++){
if (!viz[i]) {
dfsSortTop(i);
}
}
while(!noduriSortTop.empty()){
fout<<noduriSortTop.top()<< " ";
noduriSortTop.pop();
}
}
int main() {
int n, m;
fin >> n >> m;
graf G(n, m);
for(int i = 0; i < m; i ++){
int n1, n2;
fin >> n1 >> n2;
G.adaugaInListaAd(n1, n2);
}
G.sortareTopologica();
return 0;
}