Cod sursa(job #1378960)

Utilizator vlady1997Vlad Bucur vlady1997 Data 6 martie 2015 15:17:53
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>
#include <list>
using namespace std;
vector <int> g[100001], sol;
vector <int> :: iterator it;
list <int> q;
void euler (int x)
{
    int nod, y; q.push_back(x);
    while (!q.empty())
    {
        nod=q.back();
        if (!g[nod].empty())
        {
            y=g[nod].back();
            q.push_back(y);
            g[nod].pop_back();
            for (it=g[y].begin(); it!=g[y].end(); it++)
            {
                if (*it==nod)
                {
                    g[y].erase(it);
                    break;
                }
            }
        }
        else
        {
            sol.push_back(nod);
            q.pop_back();
        }
    }
}
int main()
{
    int n, m, i, x, y;
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (i=1; i<=n; i++)
    {
        if(g[x].size()%2==1)
        {
            printf("-1");
            return 0;
        }
    }
    euler(1);
    for (i=0; i<sol.size(); i++)
    {
        printf("%d ",sol[i]);
    }
    return 0;
}