Cod sursa(job #1525686)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 15 noiembrie 2015 13:41:20
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <string.h>
#include <vector>

#define pb push_back

using namespace std;

const int MN = 100005;
const int MM = 500005;

int K,N,M,S[MM];
vector<int> G[MN],Sol;

int Nextint()
{
    char S[100];
    int Num = 0,i = 0;
    bool Neg = 0;

    scanf("%s",S);

    if (S[0] == '-')
        Neg = 1,i++;

    for (;i < strlen(S);i++)
        Num = Num * 10 + (S[i] - '0');

    if (Neg)
        Num *= -1;

    return Num;
}

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

     N = Nextint();
     M = Nextint();

      for (int i = 1;i <= M;i++)
      {
          int X,Y;
          X = Nextint();
          Y = Nextint();
          G[X].pb(Y);
          G[Y].pb(X);
      }

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

    S[1] = 1;
    K = 1;

    while (K)
    {
        if (G[S[K]].empty())
            Sol.pb(S[K--]);
        else
        {
            S[++K] = G[S[K-1]][0];
            G[S[K-1]].erase(G[S[K-1]].begin());

            for (vector<int>::iterator it = G[S[K]].begin();it != G[S[K]].end();it++)
                if (*it == S[K-1])
                {
                    G[S[K]].erase(it);
                    break;
                }
        }
    }
    for (int i = 0;i <Sol.size();i++)
        printf("%d ",Sol[i]);

        printf("\n");

    return 0;
}