Cod sursa(job #2667903)

Utilizator marian222200Dimofte Marian marian222200 Data 4 noiembrie 2020 01:13:02
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#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;
}