Cod sursa(job #3126050)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 5 mai 2023 13:42:35
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;
const int MMAX = 5e5;

int n,m;
int f[NMAX + 5];
bool er[MMAX + 5];
vector<int>g[NMAX + 5];
pair<int,int>e[MMAX + 5];
vector<int>ans;

void euler(int nod)
{
    //cout << nod << ' ';
    while (f[nod] < g[nod].size())
    {
        int ind = g[nod][f[nod]++];
        if (!er[ind])
        {
            int alt = e[ind].first + e[ind].second - nod;
            er[ind] = true;
            euler(alt);
        }
    }
    ans.push_back(nod);
}

int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        in >> e[i].first >> e[i].second;
        g[e[i].first].push_back(i);
        g[e[i].second].push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        if (g[i].size() % 2 == 1)
        {
            out << -1;
            return 0;
        }
    }
    euler(1);
    if (ans.size() != m + 1)
    {
        out << -1;
        return 0;
    }
    for (int i = 0; i < ans.size(); i++)
        out << ans[i] << ' ';
    return 0;
}