Cod sursa(job #2735053)

Utilizator ViAlexVisan Alexandru ViAlex Data 1 aprilie 2021 19:31:22
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 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+10;
 
struct edge{
	int a,b;
	bool used;
};
 
int n,m,degree[mx];
 
vector<int> g[mx];
vector<edge> edges;
 
void read(){
	in>>n>>m;
	int a,b,cnt=0;
	edges.reserve(mx*5);

	for(int i=0;i<m;i++){
		in>>a>>b;
		g[a].push_back(cnt);
		g[b].push_back(cnt);
 
		degree[a]++;
		degree[b]++;
 
		edges.push_back({a,b});
		cnt++;
	}
}
 
void euler(int node){
	while(!g[node].empty()){
		int index=g[node].back();
		g[node].pop_back();
 
		if(edges[index].used){
			continue;
		}
		int next=edges[index].a+edges[index].b-node;
		edges[index].used=true;
		euler(next);
	}
	out<<node<<" ";
}
 
void solve(){
	for(int i=1;i<=n;i++){
		if(degree[i]%2==1){
			out<<-1;
			return;
		}
	}
	euler(1);
}
 
int main(){
	read();
	solve();
	return 0;
}