Cod sursa(job #2422868)

Utilizator budurlean.andreiBudurlean Andrei budurlean.andrei Data 20 mai 2019 09:32:26
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <tuple>
#include <stack>

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

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

void ReadData();
bool IsEulerian();
void DetCicle(int x);
void Write();

int main()
{
    ReadData();
    if (!IsEulerian())
        fout << "-1";
    else
    {
        DetCicle(1);
        Write();
    }
}

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

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

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

bool IsEulerian()
{
    for (int x = 1; x <= n; ++x)
        if (G[x].size() % 2 == 1)
            return false;
    return true;
}
void DetCicle(int x)
{
    VIT p = VIT(n + 1);
    for (int i = 1; i <= n; ++i)
        p[i] = G[i].begin();

    int y, e;
    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()
{
    //fout << ce.size() << '\n';
    for (size_t i = 0; i < ce.size() - 1; ++i)
        fout << ce[i] << ' ';
}