Cod sursa(job #735599)

Utilizator visanrVisan Radu visanr Data 16 aprilie 2012 20:52:57
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

#define nmax 100010
#define pb push_back

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<long> graph[nmax];
vector<long> solution;
long n,m,x,y;

void read_input()
{
     in>>n>>m;
     for(long i=0;i<m;i++)
     {
              in>>x>>y;
              graph[x].pb(y);
              graph[y].pb(x);
     }
}

int Eulerian()
{
     for(long i=1;i<=n;i++) if(graph[i].size()%2) return 0;
     return 1;
}

void euler(long start)
{
     stack <long> s;
     s.push(start);
     while(!s.empty())
     {
                      long node=s.top();
                      while(!graph[node].empty())
                      {
                                                 long nextNode= *graph[node].begin();
                                                 graph[nextNode].erase(find(graph[nextNode].begin(),graph[nextNode].end(),node));
                                                 graph[node].erase(graph[node].begin());
                                                 s.push(nextNode);
                                                 node=nextNode;
                      }
                      solution.pb(s.top());
                      s.pop();
     }
     solution.pop_back();
     for(int i=0;i<solution.size();i++) out<<solution[i]<<' ';
}

int main()
{
    int i;
    read_input();
    if(Eulerian()) euler(1);
    else out<<-1<<'\n';
    in.close();
    out.close();
    return 0;
}