Cod sursa(job #1660254)

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

using namespace std;

#define MAX 100001

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

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);
            vector<int>::iterator it;
            for(it=ans.begin();it<ans.end();++it)
              g<<*it<<" ";
        }

    return 0;
}

void DFS(int node)
{
   if(V[node].empty())return;
   int i;
   vector<int>::iterator it;
  // g<<node<<" ";
   ans.push_back(node);

   for(i=1;i<=Vect[node];++i)
    {
        ans.push_back(node);
    }        //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;
        }

   DFS(i);
}