Cod sursa(job #419303)

Utilizator codyCodreanu Ionut cody Data 17 martie 2010 11:53:37
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream.h>
#include<iostream.h>
struct nod{
int evenim;
nod *urm;
} *cap[50001];


ofstream g("sortaret.out");

int initializare(int n,int v[50001]){
int i;
for (i=1;i<=n;i++)
	v[i]=0;
return 0;
}
int adaugare(int i,int j){
nod *aux,*p;
aux=new nod;
aux->evenim=j;
aux->urm=NULL;
if(cap[i]==NULL)
	cap[i]=aux;
else{
p=cap[i];
while(p->urm!=NULL)
	p=p->urm;
p->urm=aux;
}
return 0;
}

int afisare_lista(int i){
nod *p;
p=cap[i];
while(p!=NULL){
cout<<p->evenim<<" ";
p=p->urm;
}
cout<<"\n";
return 0;
}

int citire(int &n,int &m,int v[50001]){
	int i,j,k;
	ifstream f("sortaret.in");
	f>>n>>m;
	//cout<<n<<"\n";
	initializare(n,v);
	for(k=1;k<=m;k++){
	f>>i>>j;
	//cout<<i<<" "<<j<<"\n";
	v[j]++;
	adaugare(i,j);
		}
	f.close();
	/*for(i=1;i<=n;i++){
		cout<<"\n lista "<<i<<"\n";
		afisare_lista(i);
		//cout<<v[i]<<" ";
	}*/
	return 0;
}	
 
int sortare(int n,int v[50001])
{
	int ok=0,i;
	nod *p;
	while(ok==0){
	for(i=1;i<=n;i++)
	{
	if(v[i]==0){
		g<<i<<" ";
		v[i]=-1;
		break;
		
	}
	}
	if(i>n)
		ok=1;
	else{
	p=cap[i];
	while(p!=NULL)
	{
	v[p->evenim]--;
	p=p->urm;
	}
	
	}
	}
return 0;
}
int main(){
int n,v[50001],m;
citire(n,m,v);
sortare(n,v);

}