Cod sursa(job #1599697)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 14 februarie 2016 11:26:45
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");

#define MAXN 100050

vector <int> edge[MAXN];
int N, M;

int main()
{
    fin >>N >>M;
    for (int i = 1; i <= M; ++i)
	{
		int x, y;
		fin >>x >>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for (int i = 1; i <= N; ++i)
		if (edge[i].size()%2 == 1)
		{
			fout <<-1 <<'\n';
			return 0;
		}
	stack <int> myStack;
	myStack.push(1);
	while (!myStack.empty())
	{
		int node = myStack.top();

		if (edge[node].size())
		{
			int oNode = edge[node].back();

			myStack.push(oNode);
			edge[node].pop_back();
			for (vector<int>::iterator _it = edge[oNode].begin(); _it!= edge[oNode].end(); ++_it)
				if (*_it == node)
					edge[oNode].erase(_it);
		}
		else
		{
			myStack.pop();
			if (!myStack.empty())
				fout <<node <<' ';
		}
	}
    return 0;
}