Cod sursa(job #1660235)

Utilizator CalarisPredut Denis Stefanita Calaris Data 22 martie 2016 21:43:02
Problema Ciclu Eulerian Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 100001

vector<int> V[MAX];
int Vect[MAX];

void DFS(int node);
fstream f("ciclueuler.in",ios::in);
ofstream g("ciclueuler.out");

int main()
{
    int N,M,i,x,y,OK=1;
    f>>N>>M;

    for(i=0;i<M;++i)
        {
        f>>x>>y;
        if(x==y)
            ++Vect[x];
        else
            V[x].push_back(y), V[y].push_back(x);
        }
    for(i=1;i<=N;++i)
        if(V[i].size()%2!=0)
            {
            g<<"-1";
            OK=0;
            break;
            }
    if(OK==1)DFS(1);


    return 0;
}

void DFS(int node)
{
   if(V[node].empty())return;
   int i;
   vector<int>::iterator it;
   g<<node<<" ";
   for(i=1;i<=Vect[node];++i)g<<node<<" ";
   Vect[node]=0;

   i = V[node][V[node].size()-1];
   V[node].pop_back();

   for(it=V[i].begin();it<V[i].end();++it)
     if(*it==node)
        {
            V[i].erase(it);
            break;
        }


  // g<<" "<<i;
   DFS(i);
}