Cod sursa(job #2735046)

Utilizator ViAlexVisan Alexandru ViAlex Data 1 aprilie 2021 19:20:25
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>

using namespace std;

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

const int mx=1e5+100;

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

int n,m,degree[mx];

vector<int> g[mx];
vector<edge> edges;
vector<int> q;

void read(){
	in>>n>>m;
	int a,b;
	for(int i=0;i<m;i++){
		in>>a>>b;
		g[a].push_back(edges.size());
		g[b].push_back(edges.size());

		degree[a]++;
		degree[b]++;

		edges.push_back({a,b});
	}
}

void euler(int node){
	for(int j=(int)g[node].size()-1;j>=0;j--){

		int index=g[node][j];

		g[node].pop_back();

		if(edges[index].used){
			continue;
		}

		int next=edges[index].a+edges[index].b-node;
		edges[index].used=true;
		euler(next);

	}
	q.push_back(node);
}

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

	euler(1);
	for(int k:q)
		out<<k<<" ";
}

int main(){
	read();
	solve();
	return 0;
}