Cod sursa(job #356969)

Utilizator cipriancxFMI - gr143 Timofte Ciprian cipriancx Data 17 octombrie 2009 18:27:18
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include<iostream>

using namespace std;

//definim clasa nod
class nod
{
public:

	int nr; 
	int noduri;
    int stg;
	int drp;
	int intrari;

	nod *urmator; 
	nod *ultim;
	
	nod(void):nr(0),noduri(0),stg(0),drp(0),intrari(0),urmator(NULL),ultim(NULL){};
};



//definim lista


nod v[50001];



int main(void)
{
	
	freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
	

	int n,m,i,x,y;
	
	cin>>n>>m;
	
	
	//creem vectorul cu listele de noduri
	for(i=1; i<=m; i++)
	{
		cin>>x>>y;
		
		if(v[x].noduri==0)
		{   
			nod *var=new nod;
            var->nr=y;
            var->urmator=NULL;
			v[x].noduri=1;
			v[x].urmator=var;
			v[y].intrari++;
			v[x].ultim=v[x].urmator;
		}
		
		
		
		else 
		{ 
			nod *var=new nod; 
		    
            var->nr=y;
            var->urmator=NULL;
			v[x].ultim->urmator=var;
			v[x].ultim=var;
            v[x].noduri++;
		    v[y].intrari++;
		}
	}
	
		
	
	
	
	

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

	
	
	//initializam drp-urile
	for(i=1; i<=n-1; i++)v[i].drp=i+1;
	for(i=2; i<=n; i++)v[i].stg=i-1;
	
	
	
	
	
	
	
	int noduri=n;
   	
	
	int primul=1;
	
	
	
	while(n)
	{
		int aux=primul;
	for(i=1; i<=n; i++)
	{ 
		if(v[aux].intrari==0)
		{ cout<<aux<<" ";
			if(v[aux].noduri){ int k=v[aux].noduri;
			                     
							  nod *r=v[aux].urmator;
                              
                                while(k)
								{  
                                 
                     			int auxiliar=r->nr;
							   v[auxiliar].intrari--;
							   r=r->urmator;
							   k--;
								
								} 
			                   			
			                 }
			//mai sus, daca mai are noduri, le decrementam pe toate
			
			if(primul==aux)primul=v[aux].drp; noduri--; if(v[aux].stg && v[aux].drp){ v[v[aux].stg].drp=v[aux].drp;
                                                                                         v[v[aux].drp].stg=v[aux].stg; 
		                                                                                 }
 		
		}
		
		aux=v[aux].drp;
	}

	n=noduri;
	
	}
	

	
	return 0;
}