Cod sursa(job #688569)

Utilizator Cezar13Cezar Manea Cezar13 Data 23 februarie 2012 17:49:01
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#define NMAX 100008
#define MMAX 500008

#define InFile "ciclueuler.in"

using namespace std;
ofstream fout("ciclueuler.out");

vector <int> G[NMAX];
int n, lgh,inc,sf,m,gr[NMAX],sol[NMAX],n_sol,n_stiva,stiva[MMAX];
struct mch {int a; int b;} muchie[MMAX];
bool vizitat[MMAX];
void Citire();
void Afisare();
void verificare();
void euler();

int main()
{
Citire();
verificare();
euler();
Afisare();
return 0;
}

void euler()
{
	stiva[++n_stiva] = 1;
    int nod; int mch_sel;
    unsigned int i;
	while (n_stiva > 0)
    {
        nod = stiva[n_stiva];
        for (i = 0; i < G[nod].size(); ++i)
        {
            mch_sel = G[nod][i];
            if (!vizitat[mch_sel])
            {
                vizitat[mch_sel] = true;
                if (muchie[mch_sel].a == nod)
                    stiva[++n_stiva] = muchie[mch_sel].b;
                else
                    stiva[++n_stiva] = muchie[mch_sel].a;
                break;
            }
        }
        if (i == G[nod].size())
        {
            sol[++n_sol] = nod;
            --n_stiva;
        }
    }
}

void Citire()
{int i, x,y;
ifstream fin(InFile);
fin>>n>>m;
for (i=1; i<=m; i++)
	{
	fin>>x>>y;
	G[x].push_back(i);
	G[y].push_back(i);
	gr[x]++; gr[y]++;
	muchie[i].a=x; muchie[i].b=y;
	vizitat[i]=false;
	}
}

void verificare()
{
	for (int i=1;i<=n;i++)
		if (gr[i]%2) 
			{
			fout<<"-1\n";
			fout.close();
			exit(0);
			}
}
	
void Afisare()
{
for (int i = n_sol; i >= 2; --i)
	fout<<sol[i]<<' ';
fout<<'\n';
fout.close();
}