Pagini recente » Cod sursa (job #1430986) | Cod sursa (job #2578257) | Cod sursa (job #2440048) | Cod sursa (job #999063) | Cod sursa (job #2202436)
#include <iostream>
#include <cstdio>
#include <queue>
#define minInfinit -2000000000
using namespace std;
class minPq
{
public :
bool operator() (const int &a, const int &b)
{
return a > b;
}
};
class Vector
{
public :
// valori
int valoare;
Vector* urm;
Vector* sfarsit;
// constructor
Vector(const int&);
// functii
friend ostream& operator<<(ostream&, const Vector&);
void adauga(const int &x);
};
Vector :: Vector(const int &x)
{
valoare = x;
urm = NULL;
sfarsit = NULL;
}
ostream& operator<<(ostream &out, const Vector &x)
{
out << x.valoare << " ";
Vector* p = x.urm;
while (p)
{
out << p->valoare << " ";
p = p->urm;
}
return out;
}
void Vector :: adauga(const int &x)
{
if (sfarsit)
{
while (sfarsit->urm)
sfarsit = sfarsit->urm;
Vector* b = new Vector(x);
sfarsit->urm = b;
sfarsit = b;
}
else
{
Vector* b = new Vector(x);
sfarsit = b;
}
if (urm == NULL)
urm = sfarsit;
}
void df(int &nod, Vector* &sortareTopologica, Vector** &muchii, int* &gradeIntrare, bool* &vizitat)
{
if (vizitat[nod] == 0)
{
vizitat[nod] = 1;
if (sortareTopologica == NULL)
sortareTopologica = new Vector(nod + 1);
else
sortareTopologica->adauga(nod + 1);
if (muchii[nod])
for (Vector* p = muchii[nod] ; p ; p = p->urm)
{
gradeIntrare[p->valoare]--;
if (gradeIntrare[p->valoare] == 0)
df(p->valoare,sortareTopologica,muchii,gradeIntrare,vizitat);
}
}
}
void drumCritic()
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
priority_queue <int, vector<int> , minPq> PQ;
int n(0);
scanf("%d",&n);
/*int* drumuri = new int[n];
for (int i = 0 ; i < n ; i++)
scanf("%d",&drumuri[i]);*/
int m(0);
scanf("%d",&m);
Vector** muchii = new Vector*[n];
for (int i = 0 ; i < n ; i++)
muchii[i] = NULL;
int *gradeIntrare = new int[n]; // de fiecare data trebuie sa initializez vectorul !
for (int i = 0 ; i < n ; i++)
gradeIntrare[i] = 0;
for (int i = 0 ; i < m ; i++)
{
int a(0), b(0);
scanf("%d %d\n",&a,&b);
a--;
b--;
gradeIntrare[b]++;
if (muchii[a] == NULL)
muchii[a] = new Vector(b);
else
muchii[a]->adauga(b);
}
Vector* sortareTopologica = NULL;
bool* vizitat = new bool[n];
for (int i = 0 ; i < n ; i++)
vizitat[i] = 0;
for (int i = 0 ; i < n ; i++)
{
if (gradeIntrare[i] == 0)
df(i,sortareTopologica,muchii,gradeIntrare,vizitat);
}
if (sortareTopologica)
cout << *sortareTopologica;
}
/// 1. La sortarea topologica, daca alegem DF, de ce trebuie sa adaugam varful de-abia la final,
/// in loc sa il adaugam la inceput ?
int main()
{
drumCritic();
return 0;
}