Cod sursa(job #1631296)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 5 martie 2016 14:36:25
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int Nmax = 100002;

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

struct Edge
{
    int x, y;
};

int n, m;
vector<vector<int>> G;
vector<int> Cycle;
vector<Edge> E;
vector<bool> v;

void Read();
inline void Dfs(int x);

int main()
{
    Read();

    for ( int i = 1; i <= n; i++ )
        if ( G[i].size() % 2 == 1 )
        {
            fout << -1;
            return 0;
        }

    Dfs(1);
    int z = Cycle.size();
    for ( int i = 0; i < z - 1; i++ )
        fout << Cycle[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> n >> m;

    G = vector<vector<int>>(n + 1);
    E = vector<Edge>(m + 1);
    v = vector<bool>(n + 1);
    int x, y;

    for ( int i = 1; i <= m; i++ )
    {
        fin >> x >> y;
        G[x].push_back(i);
        G[y].push_back(i);
        E[i] = {x, y};
    }
}

inline void Dfs(int x)
{
    while ( G[x].size() )
    {
        int y = G[x].back();
        if ( v[y] )
        {
            G[x].pop_back();
            continue;
        }
        v[y] = 1;
        Dfs(E[y].x + E[y].y - x);
    }
    Cycle.push_back(x);
}