Cod sursa(job #2081697)

Utilizator anisca22Ana Baltaretu anisca22 Data 4 decembrie 2017 23:41:26
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 500005
#define pii pair <int, int>
#define INF 0x3f3f3f3f

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

int N, M;
int gr[NMAX], used[MMAX];
vector <int> rsp;
vector <pii> v[NMAX];
stack <int> st;

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        v[x].push_back({y, i});
        v[y].push_back({x, i});
        gr[x]++, gr[y]++;
    }
    for (int i = 1; i <= N; i++)
        if (v[i].size() % 2 != 0 || v[i].size() == 0)
        {
            fout << "-1\n";
            return 0;
        }
    st.push(1);
    while (!st.empty())
    {
        int nod = st.top();
        if (gr[nod] == 0)
        {
            st.pop();
            if (!st.empty())
                rsp.push_back(st.top());
        }
        else
        {
            while (used[v[nod].back().second] == 1)
                v[nod].pop_back();
            int nxt = v[nod].back().first;
            int edge = v[nod].back().second;
            used[edge] = 1;
            gr[nod]--, gr[nxt]--;
            st.push(nxt);
        }
    }
    vector <int> :: iterator it;
    for (it = rsp.begin(); it != rsp.end(); it++)
        fout << *it << " ";
    return 0;
}