Cod sursa(job #2200479)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 1 mai 2018 16:04:49
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define dimn 100005
#define dimm 500005

std::ifstream f("ciclueuler.in");
std::ofstream g("ciclueuler.out");
//#define f std::cin
//#define g std::cout

int N, M;
int x[dimm], y[dimm];
std::list <int> adj[dimn];
std::vector <int> sol;
bool seen[dimm];

bool check() {
    for(int i=1; i<=N; i++)
        if(adj[i].size()%2)
            return 0;
    return 1;
}
void dfs(int start)
{
	for(auto vec:adj[start]) {
		if(!seen[vec])
			seen[vec] = 1,
			dfs(x[vec]+y[vec] - start);
	}
    sol.push_back(start);
}

void citire() {
    f >> N >> M;
    for (int i=0; i<M; i++) {
        f >> x[i] >> y[i];
        adj[x[i]].push_back(i);
        adj[y[i]].push_back(i);
    }
}
void rezolvare() {
	if(!check()) {
		g << "-1\n";
		return;
	} dfs(x[0]);
    for(int i=1; i<sol.size(); i++)
        g << sol[i] << " ";
    g << "\n";
}

int main()
{
    citire();
    rezolvare();
    
    return 0;
}