Cod sursa(job #2122445)

Utilizator titusuTitus C titusu Data 5 februarie 2018 08:38:15
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <cassert>
#include <vector>
using namespace std;

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

int n , m;

vector<vector<int>> G;
vector<int> L;
vector<pair<int,int>> M;
vector<bool> elim;
int d[100001];

void Euler(int k)
{
	for(auto x : G[k])
	{
		//x = indicele muchiei 
		//M[x].first = k
		//M[x].second = cealalta extremitate
		if(!elim[x])
		{
			elim[x] = 1;
			int p = M[x].second;
			if(p == k)
				p = M[x].first;
			Euler(p);
		}
	}
	L.push_back(k);
}

int main()
{
    int i , j;
    fin >> n >> m;
    G.resize(n + 1);
    M.resize(m);
    elim.resize(m, false);
    for(int k = 0 ; k < m ; k ++)
    {
		fin >> i >> j;
		d[i] ++, d[j] ++;
		M[k] = {i,j};
		
		G[i].push_back(k);
		G[j].push_back(k);
    }
    bool ok = true;
    for(int i =1 ; i <= n ; i ++)
		if(d[i] % 2 == 1)
			ok = false;
	if(!ok)
		fout << -1;
	else
	{
		Euler(1);
		
		for(int i = 0 ; i < L.size() -1 ; i ++)
			fout << L[i] << " ";
	}
	return 0;
	
}