Cod sursa(job #1873043)

Utilizator musashi1Doros Doru-Lucian musashi1 Data 8 februarie 2017 19:09:29
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb

#include <vector>
#include <list>
#include<queue>
#include<stack>
#include<fstream>
#include <cstring>
#define MAXN 100001
#define MAXM 500001
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

stack<int> S;

int n, m, C[MAXM], nc=0;
//char G[MAXN][MAXM];

static vector <int> viz[MAXN];
vector <int> g[MAXN];



void euler(int nod)
{
	int dd,xx,urm;
	for (urm = 0; urm < g[nod].size(); urm++)
	if (viz[nod][urm])
	{
		dd = viz[nod][urm];
		
		for (int i = 0; i < g[viz[nod][urm]].size(); i++) 
		{
			xx = viz[viz[nod][urm]][i];
			if (xx == nod){ viz[viz[nod][urm]][i] = 0; break; }
		}

		viz[nod][urm] = 0;		
			euler(dd);

	}
	//S.pop();
	C[nc++] = nod;
	
}
int main()
{
	int a, b;
	fin >> n>> m;


	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		g[x].push_back(y);
		if (x != y)
		g[y].push_back(x);
		
		viz[x].push_back(y);
		if (x != y)
		viz[y].push_back(x);
	}

	euler(1);
	if (nc!=0)
	for (int i = 0; i < nc-1; i++)
	{
		fout << C[i]<<' ';
	}
	else
	{
		fout << '-1';
	}

}