Cod sursa(job #1919759)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 9 martie 2017 20:56:53
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 500005;
int N, st[Nmax], dr[Nmax], poz[Nmax], ans[Nmax], head;
vector <int> L[Nmax / 5];
bool used[Nmax];

inline void Read()
{
    int M, i;
    fin >> N >> M;
    for(i = 1; i <= M; i++) {
        fin >> st[i] >> dr[i];
        L[st[i]].push_back(i);
        L[dr[i]].push_back(i);
    }
    fin.close();
}

inline bool Euler()
{
    int i;
    for(i = 1; i <= N; i++) {
        if(L[i].size() & 1) return false;
    }
    return true;
}

inline void DFS(int nod)
{
    while(poz[nod] < L[nod].size()) {
        int nnod = L[nod][poz[nod]++];
        if(!used[nnod]) {
            used[nnod] = 1;
            DFS(st[nnod] + dr[nnod] - nod);
        }
    }
    ans[++head] = nod;
}

inline void Solve()
{
    if(!Euler()) {
        fout << "-1\n";
    }
    else {
        int i;
        DFS(1);
        head--;
        do {
            fout << ans[head] << " ";
        } while(--head);
    }
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}