Cod sursa(job #735610)

Utilizator visanrVisan Radu visanr Data 16 aprilie 2012 21:05:30
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;

#define nmax 100010

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

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

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

void euler(int start)
{
     stack <int> s;
     s.push(start);
     int node,nextNode;
     while(!s.empty())
     {
                      node=s.top();
                      while(!graph[node].empty())
                      {
                                                 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.push_back(s.top());
                      s.pop();
     }
     solution.pop_back();
     for(vector<int>::iterator it=solution.begin();it!=solution.end();++it) out<<*it<<" ";
     out<<"\n";
}

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