Cod sursa(job #292594)

Utilizator Ionescu_MariaIonescu Maria-Dorina Ionescu_Maria Data 31 martie 2009 12:09:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream.h>
unsigned int a[10000][10000], s[50000], n,nrp[50000];
//Algoritm de sortare topologica
void cit()
{
	unsigned int x,y;
	long m;
	ifstream fin("sortaret.in");
	fin>>n>>m;
	while(m--)
	{
		fin>>x>>y;
		a[x][y]=1;
	}
	fin.close();
}
void constr_s()
{
	unsigned int  i,j,nc;
	nc=0;
	for(j=1;j<=n;j++)
	{
		nrp[j]=0;
		for(i=1;i<=n;i++)
			nrp[j]+=a[i][j];
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			if(nrp[j]==0)
				{
					nc=j;
					break;
				}
		s[i]=nc;
		nrp[nc]=1002;
		for(j=1;j<=n;j++)
			if(a[nc][j]==1)
				nrp[j]--;
	}
}
void afis()
{
	unsigned int i;
	ofstream fout("sortaret.out");
	for(i=1;i<=n;i++)
		fout<<s[i]<<" ";
	fout<<'\n';
	fout.close();
}
int main()
{
	cit();
	constr_s();
	afis();
	return 0;
}