Cod sursa(job #1614245)

Utilizator ZenusTudor Costin Razvan Zenus Data 25 februarie 2016 21:10:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 100009;
const int mmax = 500009;

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

vector < int > g[nmax];
int st[mmax] , mark[nmax] , p[mmax];
int n , m , top , i , x , y , sp;

int df(int x)
{
    int r = 1;
    for (int i = 0 ; i < g[x].size() ; ++i)
    {
        int y = g[x][i];
        if (mark[y]) continue;

        mark[y] = 1;
        r += df(y);
    }
    return r;
}

bool check()
{
    for (i = 1 ; i <= n ; ++i)
    if (g[i].size() % 2)
    return 0;

    if (df(1) < n) return 0;
    return 1;
}

void solve(int x)
{
    while (g[x].size())
    {
        st[++top] = x;
        int y = g[x].back();
        g[x].pop_back();

        for (vector < int > :: iterator it = g[y].begin() ; it != g[y].end() ; ++it)
        if (*it == x)
        {
            g[y].erase(it);
            break;
        }

        x = y;
    }
}

void euler(int x)
{
    while (true)
    {
        solve(x);
        x = st[top--];

        p[++sp] = x;
        if (top == 0) break;
    }

    for (int i = 1 ; i <= sp ; ++i)
    fout << p[i] << " ";
}

int main()
{

fin >> n >> m;

for (i = 1 ; i <= m ; ++i)
{
    fin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
}

if (check())
euler(1);
else
fout << "-1" << '\n';

return 0;
}