Cod sursa(job #751820)

Utilizator Marius96Marius Gavrilescu Marius96 Data 27 mai 2012 00:34:09
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<vector>
#include<set>
using std::vector;
using std::set;

vector<int> v[100005];
set<int>  del[100005];
bool        d[100005];
bool        p[100005];
bool isfirst=true;

void euler (int x)
{
	bool first=isfirst;
	isfirst=false;
	while(!v[x].empty()){
		int w=-1;
		do{
			if(del[x].count (w))
				del[x].erase (w);
			w=*v[x].rbegin();
			v[x].pop_back();
		}while(del[x].count (w)&&!v[x].empty());
		if(del[x].count (w))
			break;
		del[w].insert (x);
		euler (w);
	}
	if(!first)
		printf ("%d ",x);
}

void dfs (int x)
{
	p[x]=1;
	for(vector<int>::iterator it=v[x].begin();it!=v[x].end();it++)
		if(!p[*it])
			dfs (*it);
}

int main()
{
	freopen ("ciclueuler.in","r",stdin);
	freopen ("ciclueuler.out","w",stdout);
	int n,m;
	scanf ("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf ("%d%d",&x,&y);
		v[x].push_back (y);
		v[y].push_back (x);
		d[x]^=1;
		d[y]^=1;
	}
	dfs (1);
	for(int i=1;i<=n;i++)
		if(d[i]||!p[i]){
			puts ("-1");
			return 0;
		}
	euler (1);
	return 0;
}