Cod sursa(job #2030233)

Utilizator mihai.alphamihai craciun mihai.alpha Data 1 octombrie 2017 12:40:36
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <vector>
#include <stack>

#define MAXN (int)1e5
#define MAXM (int)5e5

FILE *fin, *fout;

int N, M;

int fr[MAXM + 1], to[MAXM + 1];
std::vector <int> v[MAXN + 1];
std::stack <int> st;
bool viz[MAXM + 1];
std::vector <int> ans;

int main() {
	fin = fopen("ciclueuler.in", "r");
	fout = fopen("ciclueuler.out", "w");
	fscanf(fin, "%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		int x, y;
		fscanf(fin, "%d%d", &x, &y);
		fr[i] = x, to[i] = y;
		v[x].push_back(i);
		v[y].push_back(i);
	}
	for(int i = 1;i <= N;i++)
		if (v[i].size() & 1) {
			fprintf(fout, "-1");
			return 0;
		}
	st.push(1);
	while (!st.empty()) {
		int nod = st.top();
		if (v[nod].size()) {
			int much = v[nod].back();
			v[nod].pop_back();
			if (!viz[much]) {
				viz[much] = 1;
				int To = to[much];
				st.push(To);
			}
		}
		else {
			st.pop();
			ans.push_back(nod);
		}
	}
	for (int i = 0; i < ans.size(); i++) {
		fprintf(fout, "%d ", ans[i]);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}