Cod sursa(job #1821536)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 3 decembrie 2016 12:03:25
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <vector>
#include <fstream>
#define NX 100000
#define MX 500000
using namespace std;

vector<int> A[NX], nd, r;
int N, M;
bool used[MX];

struct muchie{
	int s, e;
};
muchie V[MX];

int main(){
	int i, a, b;

	ifstream fin ("ciclueuler.in");
	fin >> N >> M;
	for (i=0; i<M; i++){
		fin >> a >> b;
		a--; b--;
		A[a].push_back(i);
		A[b].push_back(i);
		V[i].s=a;
		V[i].e=b;
	}
	fin.close();

	ofstream fout ("ciclueuler.out");
	for (i=0; i<N; i++)
		if (A[i].size()%2==1){
			fout << "-1\n";
			fout.close();
			return 0;
		}
	nd.push_back(0);
	while (!nd.empty()){
		i=nd.back();
		if (!A[i].empty()){
			a=A[i].back();
			A[i].pop_back();
			if (used[a]==false){
				used[a]=true;
				if (V[a].s==i)
					nd.push_back(V[a].e);
				else
					nd.push_back(V[a].s);
			}
		}
		else{
			nd.pop_back();
			r.push_back(i);
		}
	}
	for (i=0; i<r.size()-1; i++)
		fout << r[i]+1 << ' ';
	fout << '\n';
	fout.close();

	return 0;
}