Pagini recente » Cod sursa (job #1539442) | Cod sursa (job #1650300) | Cod sursa (job #1940145) | Cod sursa (job #1446639) | Cod sursa (job #2791943)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
class Graf
{
private:
int nrN, nrM; ///Numar noduri, numar muchii
vector <vector<int>> listaAd; ///lista de adiacenta graf
public:
Graf(int, int, vector <vector<int>> &);
~Graf();
void afisare(ostream&);
friend ostream& operator<<(ostream& out, Graf &g); ///supraincarcare operator <<
void sortareTopologica(ostream&, int []);
};
Graf :: Graf(int nrNoduri, int nrMuchii, vector <vector<int>> &lista)
{
nrN = nrNoduri;
nrM = nrMuchii;
listaAd = lista;
}
Graf :: ~Graf()
{
nrN = 0;
nrM = 0;
listaAd.clear();
}
void Graf :: afisare(ostream &out)
{
out << "Numar de noduri: " << nrN << "\n";
out << "Numar de muchii: " << nrM << "\n";
for (int i = 0; i < nrN; i++)
for (int j = 0; j < listaAd[i].size(); j++)
{
out << "Muchia " << i << " " << listaAd[i][j];
out << "\n";
}
}
ostream& operator<<(ostream& out, Graf &g)
{
g.afisare(out);
return out;
}
void Graf :: sortareTopologica(ostream &out, int grade[])
{
queue <int> coada;
vector <int> rez;
for (int i = 1; i <= nrN; i++)
if (grade[i] == 0)
coada.push(i);
while (!coada.empty())
{
int nod_curent = coada.front();
rez.push_back(nod_curent);
coada.pop();
for (int i = 0; i < listaAd[nod_curent].size(); i++)
{
int vecin = listaAd[nod_curent][i];
grade[vecin]--;
if (grade[vecin] == 0)
coada.push(vecin);
}
}
for (int i = 0; i < rez.size(); i++)
out << rez[i] << " ";
}
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m, st, dr, grade[50001] = {0};
fin >> n >> m;
vector <vector<int>> listaAd (n + 1);
for (int i = 1; i <= m; i++)
{
fin >> st >> dr;
listaAd[st].push_back(dr);
grade[dr]++;
}
Graf g(n, m, listaAd);
g.sortareTopologica(fout, grade);
fin.close();
fout.close();
return 0;
}