Cod sursa(job #2574832)

Utilizator mirceatlxhaha haha mirceatlx Data 6 martie 2020 10:12:34
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <stack>
#define MaxNumberOfNodes 100005
using namespace std;

ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");

int N, M, deg[MaxNumberOfNodes];
bool visited[MaxNumberOfNodes];
vector < pair < int , int > > Graph[MaxNumberOfNodes];
vector <int> Answer;
stack <int> Stack;

void Euler()
{
	int currentNode, nextNode;
	Stack.push(1);
	while(!Stack.empty()){
		currentNode = Stack.top();
		while(!Graph[currentNode].empty() && visited[Graph[currentNode].back().first]){
			Graph[currentNode].pop_back();
		}
		if(!Graph[currentNode].empty()){
			nextNode = Graph[currentNode].back().second;
			visited[Graph[currentNode].back().first] = true;
			Graph[currentNode].pop_back();
			Stack.push(nextNode);
		}
		else{
			Stack.pop();
			if(!Stack.empty()){
				Answer.push_back(Stack.top());
			}
		}
	}
}

int main()
{
	int nodeX, nodeY;
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		cin >> nodeX >> nodeY;
		Graph[nodeX].push_back(make_pair(i,nodeY));
		deg[nodeX]++;
		deg[nodeY]++;
		Graph[nodeY].push_back(make_pair(i,nodeX));	
	}
	for(int i = 1; i <= N; i++){
		if(deg[i] % 2 != 0){
			cout << -1 << "\n";
			return 0;
		}
	}
	Euler();
	for(int i = 0; i < Answer.size(); i++){
		cout << Answer[i] << " ";
	}
	return 0;
}