Cod sursa(job #710541)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 9 martie 2012 21:42:34
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <stack>
#include <queue>
#include <vector>
#define MAXN 100010
using namespace std;
bool done,viz[MAXN];
stack<int>S;
queue<int>Q;
vector<int> v[MAXN];
int deg[MAXN],m,n;	

ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");

void dfs(int x)
{
	viz[x]=1;
	for(int i=0;i<v[x].size();i++)
	if(!viz[v[x][i]]) dfs(v[x][i]);
}
void sterge(int x,int y)
{
	int i;
	v[x].erase(v[x].begin());
	for(i=0;i<v[y].size();i++) if(v[y][i]==x) break;
	v[y].erase(v[y].begin()+i);
}
void euler(int x)
{
	while(1)
	{
		if(v[x].size()==0) break;
		int y=v[x][0];
		S.push(x);
		sterge(x,y);
		x=y;		
	}
}
void solve(int x)
{
	do
	{
		euler(x);
		x=S.top(); S.pop();
		Q.push(x);
	} while(!S.empty());
	while(!Q.empty())
	{
		fo<<Q.front()<<" ";
		Q.pop();
	}
}
int main()
{
	int i,x,y;
	fi>>n>>m;
	for(i=1;i<=m;i++)
	{
		fi>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		deg[x]++; deg[y]++;
	}
	dfs(1);
	for(i=1;i<=n;i++) if(deg[i]%2 or !viz[i]) done=1;
	if(done) { fo<<"-1\n"; return 0; }
	solve(1);
	return 0;
}