Cod sursa(job #653037)

Utilizator titeltitel popescu titel Data 27 decembrie 2011 08:47:08
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<vector>
#define maxn 100002
#define maxm 500002
using namespace std;
int n,m,x,y,viz[maxn],D[maxn],S[maxm],T[maxm];
vector <pair<int,int > >G[maxn];
void citire()
{	freopen("ciclueuler.in","r",stdin); freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{	scanf("%d%d",&x,&y);
		G[x].push_back(make_pair(y,i)); D[x]++;
		G[y].push_back(make_pair(x,i)); D[y]++;
	}
}
void dfs(int x)
{	viz[x]=1;
	for(int i=0; i<G[x].size();++i)
		if(!viz[G[x][i].first]) dfs(G[x][i].first);
}
void euler ()
{	int k=1; S[k]=1;
	while(k)
	{	if(G[S[k]].empty()) {printf("%d ",S[k]); --k;}
			else{if(T[G[S[k]][G[S[k]].size()-1].second]) G[S[k]].pop_back();
					else{S[++k]=G[S[k-1]][G[S[k-1]].size()-1].first;
						 T[G[S[k-1]][G[S[k-1]].size()-1].second]=1;
						}
				}
	}
}
int main()
{	citire();
	dfs(1);
	for(int i=1; i<=n;++i)
		if((!viz[i]&&D[i])||(D[i]%2)){printf("-1\n"); return 0;}
	euler(); printf("\n"); return 0;
}