Cod sursa(job #1132998)

Utilizator ScintilloSami Kalliomaeki Scintillo Data 4 martie 2014 11:18:27
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
/* 
 * File:   main.cpp
 * Author: guest-xR8Lu6
 *
 * Created on 3. maaliskuuta 2014, 10:44
 */


#include <iostream>
#include <vector>
#include <map>
#include <cassert>

using namespace std;

struct Node
{
    map<int, int> paths;
};

vector<Node> nodes;

int nodeCount, edgeCount;
vector<int> route;


void go(int i)
{
    while(nodes[i].paths.size() > 0)
    {
        map<int, int>::iterator it = nodes[i].paths.begin();
        int j = it->first;

        it->second--;
        if(it->second == 0)
        {
            nodes[i].paths.erase(j);
        }
        
        
        
        
        
        if(i != j)
        {
            nodes[j].paths[i]--;
            if(nodes[j].paths[i] == 0)
                nodes[j].paths.erase(i);
        }

        go(j);
    }
    
    route.push_back(i);
}

int main()
{
    cin >> nodeCount >> edgeCount;
    
    nodes.resize(nodeCount);
    
    for(int i = 0; i < edgeCount; i++)
    {
        int a, b;
        cin >> a >> b;
        
        a--; b--;
        
        nodes[a].paths[b]++;
        if(a != b) nodes[b].paths[a]++;
    }
    
    for(int i = 0; i < nodeCount; i++)
    {
        int total = 0;
        
        for(map<int, int>::iterator it = nodes[i].paths.begin(); it != nodes[i].paths.end(); it++)
        {
            if(it->first == i)
                total += it->second;
            
            total += it->second;
        }
        
        if(total % 2 != 0)
        {
            cout << "-1" << endl;
            return 0;
        }
    }
    
    go(0);
    
    for(int i = 0; i < route.size() - 1; i++)
    {
        cout << (i ? " " : "") << route[i] + 1;
    }
    
    cout << endl;
    
    return 0;
}