Cod sursa(job #2805971)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 22 noiembrie 2021 10:42:44
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define MAXN 100005
int n, m, x, y, nc, nr, k;
vector<int> G[MAXN];
deque<int> Q;
bool ok;
void euler(int nod)
{
    vector<int>::iterator it;
    Q.push_back(nod);
    while(!Q.empty()){
        x = Q.front();
        if (G[x].empty()){
            Q.pop_front();
            fout << x << ' ';
        }else{
            int i = G[x].back();
            Q.push_front(i);
            G[x].pop_back();
            for (it=G[i].begin();it!=G[i].end();++it){
                if (*it == x){
                    G[i].erase(it);
                    break;
                }
            }
        }
    }
}
bool este_euler()
{
    for (int i=1;i<=n;i++){
        if (G[i].size() % 2 != 0){
            return false;
        }
    }
    return true;
}
int main() {
    fin >> n >> m;
    for (int i=1;i<=m;i++){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    if (!este_euler()){
        fout << -1 << '\n';
        return 0;
    }

    euler(1);
    return 0;
}