Cod sursa(job #2981944)

Utilizator PingStrpewpewpac PingStr Data 19 februarie 2023 11:17:49
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define N 100001
#define M 500001

using namespace std;

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

int n, m, i, j, nod, cnt;
bool used[M];
vector<int> gr[N];
list<int> ls;
stack<int> st;
pair<int, int> vf[M];

void euler (int k)
{
    st.push(k);
    while (!st.empty())
    {
        int nod = st.top();
        if (!gr[nod].empty())
        {
            int e = gr[nod].back();
            gr[nod].pop_back();
            if (!used[e])
            {
                used[e] = 1;
                if (nod == vf[e].first)
                    st.push(vf[e].second);
                else
                    st.push(vf[e].first);
            }
        }
        else
        {
            st.pop();
            ls.push_back(nod);
        }
    }
}

int main()
{
    fin>>n>>m;
    for (int k = 1; k <= m; k++)
    {
        fin>>i>>j;
        gr[i].push_back(k);
        gr[j].push_back(k);
        vf[k] = {i, j};
    }
    for (int i = 1; i <= n; i++)
    {
        if (gr[i].size() % 2 == 1)
        {
            fout<<"-1\n";
            return 0;
        }
    }
    euler(1);
    for (auto i: ls)
        fout<<i<<" ";
    fin.close();
    fout.close();
    return 0;
}