Pagini recente » Cod sursa (job #2794748) | Cod sursa (job #1050399) | Cod sursa (job #1182836) | Cod sursa (job #1676752) | Cod sursa (job #356807)
Cod sursa(job #356807)
#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;
}