Cod sursa(job #431084)

Utilizator GotenAmza Catalin Goten Data 31 martie 2010 17:32:17
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<vector>
#define nmax 100100
using namespace std;
vector <pair <int,int> > v[nmax];
int u[nmax],st[nmax],w[5*nmax],sol[nmax];
int n;
void dfs(int nod)
{
	u[nod]=1;
	vector<pair <int,int> >:: iterator fiu;
	for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
		if(!u[(*fiu).first])
			dfs((*fiu).first);
}
int ok()
{
	dfs(1);
	for(int i=1;i<=n;i++)
		if(!u[i])
			return 0;
	int	zero=0,i;
	for(i=1;i<=n&&!zero;i++)
		if(v[i].size()%2)
			zero=1;
	return 1^zero;
}
int main()
{
	int m,i,x,y,k=0,done;
	ifstream f("ciclueuler.in");
	ofstream g("ciclueuler.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		v[x].push_back(make_pair(y,i));
		v[y].push_back(make_pair(x,i));
	}
	if(!ok())
	{
		g<<"-1";
		return 0;
	}
	st[++k]=1;
	while(k)
	{
		done=0;
		while(!v[st[k]].empty()&&!done)
		{
			if(!w[v[st[k]].back().second])
			{
				st[k+1]=v[st[k]].back().first;
				w[v[st[k]].back().second]=1;
				done=1;
			}
			else
				v[st[k]].pop_back();
		}
		if(done)
			k++;
		else
			sol[++sol[0]]=st[k--];
	}
	for(i=1;i<sol[0];i++)
		g<<sol[i]<<' ';
	return 0;
}