Cod sursa(job #2422871)

Utilizator TudorCristian2Lechintan Tudor TudorCristian2 Data 20 mai 2019 09:35:56
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <tuple>
#include <stack>

const int MaxN = 100001;
const int MaxE = 500001;

using VI = std::vector<int>;
using VT = std::vector<std::tuple<int, int>>;
using IT = VT::iterator;
using VIT = std::vector<IT>;
using VVT = std::vector<VT>;

std::ofstream fout("ciclueuler.out");
std::bitset<MaxE> v;
VVT G;
VI ce;
int n, m;

void Read();
bool Euler();
void Solve();
void Write();

int main()
{
    Read();

    if (!Euler())
    {
        fout << "-1";
    }
    else
    {
        Solve();
        Write();
    }
}

void Read()
{
    std::ifstream fin("ciclueuler.in");

    fin >> n >> m;
    G = VVT(n + 1);

    int x = 0, y = 0;

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

bool Euler()
{
    for (int x = 1; x <= n; ++x)
    {
        if (G[x].size() % 2 == 1) return false;
    }

    return true;
}

void Solve()
{
    VIT p = VIT(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        p[i] = G[i].begin();
    }

    int x = 0, y = 0, e = 0;
    std::stack<int> stk;
    stk.push(1);

    while (!stk.empty())
    {
        x = stk.top();
        if (p[x] == G[x].end())
        {
            ce.emplace_back(x);
            stk.pop();
        }
        else
        {
            while (p[x] != G[x].end())
            {
                std::tie(y, e) = *p[x]++;
                if (v[e]) continue;

                v[e] = 1;
                stk.push(y);
                break;
            }
        }
    }
}

void Write()
{
    for (size_t i = 0; i < ce.size() - 1; ++i)
        fout << ce[i] << ' ';
}