Cod sursa(job #3214525)

Utilizator PetraPetra Hedesiu Petra Data 14 martie 2024 10:34:29
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>

#define NMAX 100002
#define MMAX 500002

using namespace std;

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

struct nod {
    int nod, muchie;
};

int n, m;
vector<nod> G[NMAX];
stack<nod> s;
bitset<MMAX> viz;
queue<int> ciclu;

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

bool admits_cycle()
{
    for (int i = 1; i <= n; i++)
        if (G[i].size() % 2 == 1)
            return false;
    return true;
}

bool euler()
{
    s.push({1, 0});
    while (!s.empty())
    {
        nod c = s.top();

        if (!G[c.nod].empty())
        {
            nod vec = G[c.nod].back();
            G[c.nod].pop_back();

            if (!viz[vec.muchie])
            {
                viz[vec.muchie] = true;
                s.push(vec);
            }
        }
        else
        {
            s.pop();
            ciclu.push(c.nod);
        }
    }
}

int main()
{
    read_data();

    if (!admits_cycle())
    {
        fout << -1;
        return 0;
    }

    euler();
    while (!ciclu.empty())
    {
        fout << ciclu.front() << " ";
        ciclu.pop();
    }
    return 0;
}