Cod sursa(job #1247527)

Utilizator geniucosOncescu Costin geniucos Data 22 octombrie 2014 22:13:19
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
#include<vector>

using namespace std;

int u, n, m, stiva[500009];

vector < int > vecini[100009];
vector < int > ans;

void Sterg (int X, int Y)
{
    for (vector < int > :: iterator it = vecini[X].begin(); it != vecini[X].end(); it ++)
        if (*it == Y)
        {
            vecini[X] . erase (it);
            return ;
        }
}

int main()
{

freopen ("ciclueuler.in", "r", stdin);
freopen ("ciclueuler.out", "w", stdout);

//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &n, &m);
for (int i=1; i<=m; i++)
{
    int X, Y;
    scanf ("%d %d", &X, &Y);
    vecini[X].push_back(Y);
    vecini[Y].push_back(X);
}

for (int i=1; i<=n; i++)
    if (vecini[i].size()%2 == 1)
    {
        printf ("-1\n");
        return 0;
    }

u = 1;
stiva[1] = 1;

while (u)
{
    if (vecini[stiva[u]].empty())
        ans.push_back(stiva[u--]);
    else
    {
        stiva[++u] = vecini[stiva[u-1]][0];
        vecini[stiva[u-1]].erase(vecini[stiva[u-1]].begin());
        Sterg (stiva[u], stiva[u-1]);
    }
}

for (int i=0; i<ans.size() - 1; i++)
    printf ("%d ", ans[i]);
printf ("\n");
return 0;
}