Cod sursa(job #807989)

Utilizator RaduDoStochitoiu Radu RaduDo Data 6 noiembrie 2012 00:08:59
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
#include<vector>
#define mp make_pair
#define pb push_back
#define maxn 100005
#define maxm 500005
using namespace std;
vector < pair < int , int > > L[maxn];
int m_sel[maxm],n,m,i,x,y,sel[maxn],castig[maxn],ct,ev;

void euler(int x) {
  sel[x] = 1;

  for (int i = 0; i < (int) L[x].size(); i++) {
    int y, muchie;

    y = L[x][i].first;
    muchie = L[x][i].second;

    if (m_sel[muchie]) {
      continue;
    }

    m_sel[muchie] = 1;
    euler(y);
    castig[++ct] = x;
  }
}

int main()
{
	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);
		L[x].pb(mp(y,i));
		L[y].pb(mp(x,i));
	}
	ev=0;
	for(i=1;i<=n;++i)
		if(L[i].size()%2==1)
		{
			printf("-1\n");
			break;ev=1;
		}
	if(ev==0)
	{
	for(i=1;i<=n;++i)
		if(!sel[i]&&L[i].size()%2==0)
			euler(i);
		for(i=1;i<=ct;++i)
			printf("%d ",castig[i]);
	}
	return 0;
}