Cod sursa(job #1567787)

Utilizator bpalaniciPalanici Bogdan bpalanici Data 13 ianuarie 2016 18:58:02
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int N = 100005;
const int M = 500005;

int n, m;
int grad[N];
vector < vector < pair <int, int> > > graf;
vector <int> rez;
bitset <M> vizm;
bool vizn[N];

void dfs(int nod)
{
    vizn[nod] = true;
    for (const auto &it : graf[nod])
        if (!vizn[it.f])
        dfs(it.f);
}

void euler(int start)
{
    vector <int> stiva;
    stiva.push_back(start);
    while (!stiva.empty())
    {
        int nod = stiva.back();
        if (graf[nod].empty())
        {
            rez.push_back(nod);
            stiva.pop_back();
            continue;
        }
        if (vizm[graf[nod].back().s])
        {
            graf[nod].pop_back();
            continue;
        }
        stiva.push_back(graf[nod].back().f);
        vizm[graf[nod].back().s] = true;
        graf[nod].pop_back();
    }
}

int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d %d", &n, &m);
    graf.resize(n + 2);
    for (int i = 1, a, b; i <= m; i++)
        scanf("%d %d", &a, &b),
        graf[a].push_back(make_pair(b, i)),
        graf[b].push_back(make_pair(a, i)),
        grad[a]++, grad[b]++;
    dfs(1);
    for (int i = 1; i <= n; i++)
        if (!vizn[i] || grad[i] & 1)
        {
            printf("-1");
            return 0;
        }
    euler(1);
    rez.pop_back();
    for (const auto &it : rez)
        printf("%d ", it);
}