Cod sursa(job #2958294)

Utilizator ViAlexVisan Alexandru ViAlex Data 25 decembrie 2022 19:02:10
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<fstream>
#include<stack>
using namespace std;

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

struct edge{
	int a,b;
	bool visited;
};

int n,m;
vector<vector<edge*>> g;
vector<edge> edges;
vector<int> result;
vector<int> progress;

void read(){
	in>>n>>m;
	g.resize(n+1);
	progress.resize(n+1);
	edges.resize(m);
	int a,b;
	for(int i=0;i<m;i++){
		in>>a>>b;
		edges[i] = {a,b,false};

		g[a].push_back(&edges[i]);
		g[b].push_back(&edges[i]);
	}
}

void solve(){
	for(int i=1;i<=n;i++){
		if(g[i].size()%2==1){
			out<<-1;
			return;
		}
	}

	stack<int> s;
	s.push(1);
	while(!s.empty()){
		int here = s.top();

		while(progress[here] < (int) g[here].size() && g[here][progress[here]]->visited){
			progress[here]++;
		}

		if(progress[here] == (int) g[here].size()){
			result.push_back(here);
			s.pop();
		}
		else{
			edge* e = g[here][progress[here]];
			int next = e->a == here ? e->b : e->a;
			e->visited = true;
			progress[here]++;
			s.push(next);
		}
	}

	result.pop_back();
	for(int k:result){
		out<<k<<" ";
	}
}


int main(){
	read();
	solve();

	return 0;
}