Cod sursa(job #1452453)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 20 iunie 2015 22:14:30
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <vector>
#define NMax 100005
#define MMax 500005
#define pb push_back
using namespace std;

int K,N,M,S[MMax];
vector <int> G[NMax],Sol;


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

     scanf("%d%d",&N,&M);

      for (int i = 1;i <= M;i++)
      {
          int X,Y;
          scanf("%d%d",&X,&Y);
          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;
}