Cod sursa(job #796527)

Utilizator Marius96Marius Gavrilescu Marius96 Data 11 octombrie 2012 18:43:17
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<vector>
#include<stack>
using std::vector;
using std::stack;

struct str
{
	int x;
	int y;

	str()
		{
			x=y=0;
		}

	str(int xx,int yy)
		{
			x=xx;
			y=yy;
		}
}e[500005];
int ne;
vector<int> v[100005];
vector<int>::iterator its[100005];
bool u[500005];
int nr;

int m;

inline int f (int n,int m)
{
	return e[m].x+e[m].y-n;
}

void add_edge (int a,int b)
{
	v[a].push_back (ne);
	v[b].push_back (ne);
	e[ne++]=str (a,b);
}

int l=-1;
void ieuler()
{
	stack<int> s;
	int i=0,pits;

START:
	while(its[i]!=v[i].end()){
		pits=*its[i];
		if(u[pits]){
			its[i]++;
			continue;
		}
		u[pits]=1;
		its[i]++;
		s.push (i);
		i=f (i,pits);
		goto START;
	RETURN:
		;
	}
	if(l!=-1)
		printf ("%d ",i+1);
	l=0;

	if(s.empty())
		return;
	i=s.top();
	s.pop();
	goto RETURN;
}

int main()
{
	freopen ("ciclueuler.in","r",stdin);
	freopen ("ciclueuler.out","w",stdout);
	int n,m;
	scanf ("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf ("%d%d",&x,&y);
		add_edge (x-1,y-1);
	}
	for(int i=0;i<n;i++)
		its[i]=v[i].begin();
	ieuler();
	return 0;
}