Pagini recente » Cod sursa (job #3237035) | Cod sursa (job #1205773) | Cod sursa (job #645593) | Cod sursa (job #2105647) | Cod sursa (job #2667903)
#include<fstream>
#define N 50001
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int gin[N],c[N];///gin-gradul intern al unui nod, c-coada folosita la topsort
struct nod
{
int info;
nod* urm;
};
nod* l[N];///liste de muchii
nod* p;
int n,m;
void citire()
{
int i,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
p=new nod;
p->info=y;
p->urm=l[x];
l[x]=p;
gin[y]++;
}
}
void topsort()
{
int pr,ul,i,j,x;
///pr,ul-folositi la coada
pr=0;ul=-1;
for(i=1;i<=n;i++)if(gin[i]==0)c[++ul]=i;///intai bagam in coada folosita nodurile cu gradul intern 0, ele sunt primele in ordinea topologica
while(pr<=ul)///de aici in colo e algoritmul de la bfs
{
x=c[pr++];
fout<<x<<" ";
p=l[x];
while(p!=NULL)
{
j=p->info;
gin[j]--;
if(gin[j]==0)c[++ul]=j;
p=p->urm;
}
}
}
int main()
{
citire();
topsort();
return 0;
}