Cod sursa(job #356807)

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

using namespace std;

int n,m;

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){};
};

class nd
{
public:
	
int nr;
nd *urm;

nd(void):nr(0){};
};
	
	
	

nod v[50001],*p;
nd *lista,*clista;




int main(void){
	
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
clista=lista;	
	
	
	
cin>>n>>m;	
	int i,x,y;
	
	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].ultim=var;
			v[x].urmator=var;
			v[y].intrari++;
		}
		
		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++;
		}
	
	
	}
	
int aux=0;	
int sec;

for(i=1; i<=n; i++)if(v[i].noduri){aux=i; break;}

int prim=aux;


for(i=aux+1; i<=n; i++)
	if(v[i].noduri)
	
	{ 
		v[aux].drp=i;
	    v[i].stg=aux;
		aux=i;
	    
	}
	int ultima=aux;
	
	
while(prim!=ultima)
{
	sec=prim; 
	while(v[sec].intrari)sec=v[sec].drp;
	
	//adaugam nodul in lista
	nd *r=new nd;
	r->nr=sec;
	
	clista->urm=r;
	clista=r;
	
	if(prim==sec)prim=v[sec].drp;
	else{
	
	
	v[v[sec].stg].drp=v[sec].drp;
	v[v[sec].drp].stg=v[sec].stg;
	}
	
	//Aici am ramas
	
	
	cout<<sec<<" ";
	
	
	
	
	
	
	}	
	
	
	
	
	
	
	
	
	
	

	

	
	
	
	
	
	
	return 0;
}