Cod sursa(job #2781770)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 10 octombrie 2021 13:55:25
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#define VMAX 100000
#define EMAX 500000
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector < pair <int, int> > adj[VMAX];
vector <int> epath;
int V, E, x, y;
int deg[VMAX];
bool vis[EMAX];

void Euler(int src)
{
    while (!adj[src].empty())
    {
        int nxt = adj[src].back().first;
        int edge = adj[src].back().second;

        adj[src].pop_back();

        if (!vis[edge])
        {
            vis[edge] = 1;
            Euler(nxt);
        }
    }
    epath.push_back(src);
}

int main()
{
    fin >> V >> E;

    for (int i = 0; i < E; ++i)
    {
        fin >> x >> y;
        x--, y--;
        adj[x].push_back({y, i});
        adj[y].push_back({x, i});
        deg[x]++, deg[y]++;
    }

    bool ok = true;

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

    if (ok == true)
    {
        Euler(0);
        int n = epath.size();
        for (int i = 0; i <= n - 2; ++i)
                fout << epath[i] + 1 << " ";
    }
    else fout << -1;

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