Cod sursa(job #2711550)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 24 februarie 2021 13:02:36
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n,m;
vector < pair < int, int > > v[100005];
vector < int > sol;
int a,b;
int gr[100005];
int vizmuchii[500005];


int verify_odd() {
    for (int i=1;i<=n;i++) {
        if (gr[i]%2==1 || gr[i]==0) {
            return 0;
        }
    }
    return 1;
}

void euler(int k) {
    for (auto nodtoviz:v[k]) {
        if (vizmuchii[nodtoviz.second] == 0) {
            vizmuchii[nodtoviz.second] = 1;
            euler(nodtoviz.first);
        }
    }
    sol.push_back(k);
}

int main()
{
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> a >> b;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
        gr[a]++; gr[b]++;
    }
    if (verify_odd()==0) {
        g << -1;
    }
    else {
        euler(1);
        if (sol.size()!=(m+1)) {
            g << -1;
        }
        else {
            for (auto nodtoviz:sol) {
                g << nodtoviz << " ";
            }
        }
    }
    return 0;
}