Cod sursa(job #2999932)

Utilizator stefan05Vasilache Stefan stefan05 Data 11 martie 2023 18:45:24
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMAX 100005
#define MMAX 500005

using namespace std;

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

stack<int> st;

int n, m;
int x, y;
vector<pair<int, int>> l[NMAX];
vector<int> ans;
bool f[MMAX];
int i, j;

void euler(int);

int main()
{
    fin >>n>>m;
    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y;
        l[x].push_back({y, i});
        l[y].push_back({x, i});
    }

    for (i = 1; i <= n; ++i)
        if (l[i].size()%2 != 0)
        {
            fout <<-1<<'\n';

            fout.close();
            return 0;
        }

    euler(1);

    ans.pop_back();
    for (auto i: ans) fout <<i<<' ';
    fout <<'\n';
    fout.close();
    return 0;
}

void euler(int vf)
{
    pair<int, int> vfnou;

    st.push(vf);
    while (st.size())
    {
        vf = st.top();
        if (l[vf].size())
        {
            vfnou = l[vf].back();
            l[vf].pop_back();

            if (!f[vfnou.second])
            {
                f[vfnou.second] = 1;
                st.push(vfnou.first);
            }
        }
        else
            {
                st.pop();
                ans.push_back(vf);
            }
    }
}