Cod sursa(job #3213580)

Utilizator juniorOvidiu Rosca junior Data 13 martie 2024 11:56:51
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

const int NMAX = 100005, MMAX = 500005;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, nm, i, j, mc, nu, m;
vector<int> vm[NMAX], e;
int s[MMAX], d[MMAX]; // sursa, destinatie
bool u[MMAX];
stack<int> st;

bool eulerian () {
    bool e = true;
    for (int i = 1; i <= n; i++) 
        if (vm[i].size() & 1 == 1)
            e = false;
    return e;
}

int main() {
    fin >> n >> m;
    for (int im = 1; im <= m; im++) {
        fin >> i >> j;
        s[im] = i;      // sursa
        d[im] = j;      // destinatia
        u[im] = false;  // Muchia nu este utilizata.
        vm[i].push_back(im); // muchie incidenta cu i
        vm[j].push_back(im);
    }
    if (not eulerian()) {
        fout << -1;
    }
    else {
        st.push(1);


        {{
        while (not st.empty()) {
            int nod = st.top();
            if (not vm[nod].empty()) { // Exista muchie incidenta cu nodul.
                mc = vm[nod].back(); // muchia curenta
                vm[nod].pop_back(); // Consumam muchia.
                if (not u[mc]) { // Muchia nu este utilizata.
                    u[mc] = true; // muchie utilizata
                    if (d[mc] == nod) // La care capat mergem?
                        nu = s[mc]; // nodul urmator
                    else
                        nu = d[mc];
                    st.push(nu);
                }
            }
            else {
                e.push_back(nod); // Punem in ciclul eulerian.
                st.pop();
            }
        }
        }}
        for (auto nod : e)
            fout << nod << " ";
    }
    return 0;
}