Cod sursa(job #2422854)

Utilizator budurlean.andreiBudurlean Andrei budurlean.andrei Data 20 mai 2019 08:48:41
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <bitset>

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

struct Edge{
    int a, b;
};

std::ofstream fout("ciclueuler.out");
using VI = std::vector<int>;
using VVI = std::vector<VI>;
using VE = std::vector<Edge>;

std::bitset<MaxE> v;
VVI G;
VE E;
VI ce;
int n, m;

void ReadData();
bool IsEulerian();
inline void Dfs(int x);
void Write();

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

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

    fin >> n >> m;
    G = VVI(n + 1);
    E = VE(m + 1);

    for (int i = 1, a, b; i <= m; ++i)
    {
        fin >> a >> b;

        G[a].emplace_back(i);
        G[b].emplace_back(i);
        E[i] = {a, b};
    }
}

bool IsEulerian()
{
    for (int x = 1; x <= n; ++x)
        if (G[x].size() % 2 == 1)
            return false;
    return true;
}
void Dfs(int x)
{
    for (const int& e : G[x])
    {
        if (v[e]) continue;
        v[e] = 1;

        if (E[e].a == x)
            Dfs(E[e].b);
        else
            Dfs(E[e].a);
    }

    ce.emplace_back(x);
}

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