Cod sursa(job #649737)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 16 decembrie 2011 17:26:10
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;

vector <vector <int> > edges;
vector <int> degree;
stack <int> st;
int V, E;

int main(){
	freopen("ciclueuler.in", "r", stdin), freopen("ciclueuler.out", "w", stdout);
	int x, y, i;
	scanf("%d %d", &V, &E);
	vector <int> nullVector;
	edges.assign(V + 1, nullVector);
	degree.assign(V + 1, 0);
	
	for (i = 0; i < E; i++){
		scanf("%d %d", &x, &y);
		edges[x].push_back(y), edges[y].push_back(x);
		degree[x]++, degree[y]++;
	}		
	
	//verifica daca este eulerian
	for (i = 1; i <= V; i++)
		if (degree[i] % 2 == 1) {printf ("-1\n"); return 0;}
	
	//construieste ciclul
	for (i = 1; i <= V && degree[i] == 0; i++);
	st.push(i);
	
	E = E * 2;
	while (E){
		x = st.top();
		if (degree[x] == 0) st.pop();
		if (edges[x].size()){
			int y = edges[x][0];
			st.push(y);
			edges[x].erase(edges[x].begin());
			edges[y].erase(find(edges[y].begin(), edges[y].end(), x));
			degree[x]--, degree[y]--;
			E-=2;
		}
	}
	
	for (; !st.empty(); st.pop())
		printf("%d ", st.top());
	return 0;
}