Cod sursa(job #1465006)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 26 iulie 2015 11:52:18
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <vector>
#define MAX 100005
using namespace std;

int n, m, i, x, y;
bool viz[MAX];
vector<int> l[MAX];
vector<int> s;

void dfs(int v);
void EraseEdge(int v, int w);
void euler();

int main(){
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; i++){
		scanf("%d%d", &x, &y);
		l[x].push_back(y);
		l[y].push_back(x);
	}

	dfs(1);
	for(i = 1; i <= n; i++)
		if(!viz[i] || l[i].size() % 2){
			printf("-1");
			return 0;
		}

	euler();
	return 0;
}

void dfs(int v){
	viz[v] = true;

	for(int i = 0; i < l[v].size(); i++){
		int son = l[v][i];
		if(!viz[son])
			dfs(son);
	}
}

void EraseEdge(int v, int w){
	for(i = 0; i < l[w].size(); i++)
		if(l[w][i] == v){
			l[w].erase(l[w].begin() + i);
			return;
		}
}

void euler(){
	s.push_back(1);
	while(!s.empty()){
		int v = s.back();
		if(!l[v].empty()){
			int w = l[v].back();
			l[v].pop_back();
			EraseEdge(v, w);
			s.push_back(w);
		}
		else{
			printf("%d ", v);
			s.pop_back();
		}
	}
}