Cod sursa(job #2841851)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 30 ianuarie 2022 16:02:13
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>

using namespace std;

vector <vector <pair <int, int> > > G;
bitset <500005> muchii;
stack <int> St;
vector <int> ans, unde;
int N, M, x, y;

void DF(int nod) {
    for(unsigned int z = 0; z < G[nod].size(); ++z) {
        int nxt = G[nod][z].first;
        int nr = G[nod][z].second;

        if(muchii[nr] == 0) {
            muchii[nr] = 1;
            St.push(nxt);
            nod = nxt;
            z = -1;
        }
    }
}

int main() {
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    scanf("%d %d\n", &N, &M);

    G.resize(N + 2);
    unde.resize(N + 2);

    for(int i = 1; i <= M; ++i) {
        scanf("%d %d\n", &x, &y);

        G[x].push_back(make_pair(y, i));
        G[y].push_back(make_pair(x, i));
    }

    for(int i = 1; i <= N; ++i) {
        if((G[i].size() & 1) || G[i].size() == 0) {
            printf("-1\n");
            return 0;
        }
    }

    St.push(1);

    while(!St.empty()) {
        int x = St.top();

        DF(x);
        int acum = St.top();

        ans.push_back(acum);
        St.pop();
    }

    if(ans.size() - 1 != M) {
        printf("-1\n");
        return 0;
    }

    ans.pop_back();

    for(auto z: ans) {
        printf("%d ", z);
    }

    printf("\n");

    return 0;
}