Pagini recente » Cod sursa (job #379182) | Cod sursa (job #2422002) | Cod sursa (job #2041677) | Cod sursa (job #2198603) | Cod sursa (job #3000781)
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100002
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
int x,y;
vector <int> G[NMAX];
priority_queue < int , vector<int> , greater<int> > H;
int di[NMAX]; //di[x]=grad int al vf x sau -1 daca x a fost plasat pe niveluri
int nr; //nr total de noduri plasate pe nivluri
int crt[NMAX]; //nodurile de pe niv curent
void citire();
void sortare_topologica();
int main()
{
citire();
sortare_topologica();
return 0;
}
void citire()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
fin>>x>>y;
//il adaug pe y in lista de adiacenta a lui x
G[x].push_back(y);
di[y]++;
}
}
void sortare_topologica()
{
int i,x,j;
nr=0;
//daca gr int este 0, le punem pe primul nivel
for(i=1;i<=n;i++)
if(di[i]==0)
H.push(i);
while(nr<n) //pentru a merge prin toate nodurile
{
x=H.top(); //ia primul element din heap, acesta fiind minimul
H.pop(); //il scoate din heap
fout<<x<<' '; //se afiseaza acesta
nr++;
di[x]=-1;// -1 atunci cand nodul a fost plasat pe un nivel si scos din graf
//decrementez gradele int ale vecinilor lui x
for(j=0;j<G[x].size();j++) //iau un j cu care parcurg vecinii
{
di[G[x][j]]--; //scad gradul int
if(di[G[x][j]]==0) //daca gradul int a vecinului a ajuns la 0, il bag in heap
//la fiecare x nou se readauga nodurile cu gradul int 0 nu stiu cum sa mai zic
H.push(G[x][j]);
}
}
}