Cod sursa(job #2781743)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 10 octombrie 2021 13:17:45
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#define VMAX 100000
#define NOTFOUND -1

using namespace std;

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

int V, E, x, y;
vector <int> adj[VMAX];
int deg[VMAX];
stack <int> cpath;
vector <int> epath;

int getIndex(int src, int dest);
void removeEdge(int src, int dest);

void Euler(int src)
{
    int u, w;
    cpath.push(src);
    while (!cpath.empty())
    {
        u = cpath.top();
        if (adj[u].empty())
        {
            epath.push_back(u);
            cpath.pop();
        }
        else
        {
            w = adj[u][0];
            removeEdge(u, w);
            cpath.push(w);
        }
    }
    int n = epath.size();
    for (int i = n - 1; i >= 1; --i)
        fout << epath[i] + 1 << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);

    fin >> V >> E;

    while (E--)
    {
        fin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
        deg[x]++, deg[y]++;
    }

    bool ok = true;

    for (int i = 0; i < V && ok; ++i)
        if (deg[i] % 2) ok = false;

    if (ok == true) Euler(0);
    else fout << -1;

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

void removeEdge(int src, int dest)
{
    int index = getIndex(src, dest);
    if (index != NOTFOUND)
    {
        E--;
        adj[src].erase(adj[src].begin() + index);
        adj[dest].erase(adj[dest].begin() + getIndex(dest, src));
    }
}

int getIndex(int src, int dest)
{
    for (auto it = adj[src].begin(); it != adj[src].end(); ++it)
        if (*it == dest) return it - adj[src].begin();
    return NOTFOUND;
}