Cod sursa(job #665342)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 21 ianuarie 2012 22:49:55
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<cstdio>
#include<stack>
#include<list>
using namespace std;

int n,m,i,deg[100010],vis[100010],eulerian();
list<int> G[100010],SOL;
stack<int> Stack;

void read(),solve(),del(int,int),dfs(int,int&),cicle(int);


int main()
{
	read();
	solve();
	return 0;
}

void read()
{
	int x,y;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
		deg[x]++;deg[y]++;
	}
}

void solve()
{
	int v=eulerian();
	if(!v)
		printf("-1\n");
	else
	do{
		cicle(v);
		v=Stack.top();Stack.pop();
		SOL.push_back(v);
	}while(!Stack.empty());
	for(list<int>::iterator it=SOL.begin();it!=SOL.end();it++)printf("%d ",*it);
}

int eulerian()
{
	int k=0;dfs(1,k);
	if(k!=n)return 0;
	for(int i=1;i<=n;i++)if(deg[i]%2)return 0;
	return 1;
}
void dfs(int node,int &k)
{
	vis[node]=1;k++;
	for(list<int>::iterator it=G[node].begin();it!=G[node].end();it++)
	{
		if(!vis[*it])
			dfs(*it,k);
	}
}

void cicle(int node)
{
	while(!G[node].empty())
	{
		Stack.push(node);
		int next=G[node].front();
		del(node,next);
		node=next;
	}
}

void del(int u,int v)
{
	deg[u]--;deg[v]--;
	G[u].pop_front();
	for(list<int>::iterator it=G[v].begin();it!=G[v].end();it++)
	{
		if(*it==u)
		{
			G[v].erase(it);break;
		}
	}
}