Cod sursa(job #1794008)

Utilizator dnprxDan Pracsiu dnprx Data 31 octombrie 2016 19:49:56
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define nmax 500005
using namespace std;

int st[nmax], dr[nmax], q[nmax];
int N, M, K;
bool viz[nmax];
vector <int> L[nmax];

inline void Citire()
{
    freopen("ciclueuler.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        scanf("%d%d", st + i, dr + i);
        L[st[i]].push_back(i);
        L[dr[i]].push_back(i);
    }
}
inline bool Toate_Pare()
{
    for(int i = 1; i <= N; i++)
        if(L[i].size() & 1) return false;
    return true;
}

inline void DFS(int nod)
{
    for(auto it : L[nod])
        if(!viz[it])
        {
            viz[it] = true;
            DFS(st[it] + dr[it] - nod);
        }
    q[++K] = nod;
}

void Euler()
{
    freopen("ciclueuler.out", "w", stdout);
    if(!Toate_Pare()) printf("-1\n");
    else
    {
        DFS(1);
        for(int i = 1; i < K; i++)
            printf("%d ", q[i]);
        printf("\n");
    }
}

int main()
{
    Citire();
    Euler();
    return 0;
}