Cod sursa(job #3282829)

Utilizator StefanRaresStefan Rares StefanRares Data 6 martie 2025 22:02:45
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
const int NMAX = 100001, MMAX = 500001;
int n, m;
struct muchie
{
    int nod, NrM;
};
vector<muchie> G[NMAX];
vector<int> L;
stack<int> S;
bitset<MMAX> viz;
void citire()
{
    int x, y;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y;
        G[x].push_back({y, i});
        G[y].push_back({x, i});
    }
}
void Euler()
{
    muchie aux;
    int crt;
    S.push(1);
    while(!S.empty())
    {
        crt = S.top();
        if(!G[crt].empty())
        {
            aux = G[crt].back();
            G[crt].pop_back();
            if(!viz[aux.NrM])
            {
                viz[aux.NrM] = 1;
                S.push(aux.nod);
            }
        }
        else
        {
            L.push_back(crt);
            S.pop();
        }
    }
}
int main()
{
    citire();
    for(int i = 1; i <= n; i++)
        if(G[i].size() % 2 != 0)
        {
            g << "-1";
            return 0;
        }
    Euler();
    L.pop_back();
    for(const auto &x : L)
        g << x << ' ';
    f.close();
    g.close();
    return 0;
}