Pagini recente » Cod sursa (job #715435) | Cod sursa (job #1320264) | Cod sursa (job #516828) | Cod sursa (job #919375) | Cod sursa (job #2786856)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int maxim = 50001;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
class Graf{
int noduri, muchii;
//lista de adiacenta
vector<int> listaAdiacenta[maxim];
int gradeInterioare[maxim] = {0};
public:
Graf(int noduri, int muchii) : noduri(noduri), muchii(muchii) {}
void construieste(int start, int final);
void sortareTopologica();
};
void Graf::construieste(int start, int final) {
listaAdiacenta[start].push_back(final);
gradeInterioare[final]++;
}
void Graf::sortareTopologica() {
queue<int> myqueue;
for(int i = 1; i <= noduri; i++)
if (gradeInterioare[i] == 0)
{
myqueue.push(i);
}
while(!myqueue.empty())
{
int nodCurent = myqueue.front();
for(int i = 0; i < listaAdiacenta[nodCurent].size(); i++)
{
gradeInterioare[listaAdiacenta[nodCurent][i]]--;
if(gradeInterioare[listaAdiacenta[nodCurent][i]] == 0)
myqueue.push(listaAdiacenta[nodCurent][i]);
}
myqueue.pop();
cout << nodCurent << " ";
}
}
int main() {
int noduri, muchii, x, y;
in>>noduri>>muchii;
Graf mygraf(noduri, muchii);
for(int i=0; i<muchii; i++)
{
in>>x>>y;
mygraf.construieste(x, y);
}
mygraf.sortareTopologica();
in.close();
out.close();
return 0;
}