Cod sursa(job #275376)

Utilizator alecmanAchim Ioan Alexandru alecman Data 10 martie 2009 13:43:59
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include<cstdio>
#include<stack>
#include<deque>
#include<queue>

using namespace std;

#define INPUT "ciclueuler.in"
#define OUTPUT "ciclueuler.out"
#define NMAX 100001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

deque<long> List[ NMAX ], Final;
stack<long> Stiva;
queue<long> Bf;
int vis[ NMAX ];
long N, M;

//Read the input data into two <vector> class lists
void readData()
{
  long Node1, Node2;
  
  fscanf(fin, "%ld %ld", &N, &M);

  for(long i = 0; i < M; ++i)
  {  
    fscanf(fin, "%ld %ld", &Node1, &Node2);
    List[ Node1 ].push_back(Node2);
    List[ Node2 ].push_back(Node1);
  }
}

int conex()
{
  Bf.push(1);
  vis[ 1 ] = 1;

  long Node;
  deque<long>::iterator it;

  while(!Bf.empty())
  {
    Node = Bf.front();
    Bf.pop();

    for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
      if(!vis[ *it ])
      {
        Bf.push(*it);
        vis[ *it ] = 1;
      }
  }

  for(long i = 1; i <= N; ++i)
    if(!vis[ i ])
      return 0;
  return 1;
}

//Verify if each node has an even degree
int valid()
{
  if(!conex())
    return 0;

  for(long i = 1; i <= N; ++i)
    if(List[ i ].size() % 2 != 0)
      return 0;
  return 1;
}

void remove(long Node1, long Node2)
{
  List[ Node1 ].pop_front();

  deque<long>::iterator it;

  for(it = List[ Node2 ].begin(); it != List[ Node2 ].end(); ++it)
    if(*it == Node1)
    {
      List[ Node2 ].erase(it);
      break;
    }
}

void euler(long Node)
{
  long nNode;

  while(!List[ Node ].empty())
  {
    nNode = List[ Node ].front();
    Stiva.push(Node);
    remove(Node, nNode);
    Node = nNode;
  }
}

//Start building the given cycle
void solve()
{
  long Node = 1;

  do{
    euler(Node);
    Node = Stiva.top();
    Stiva.pop();
    Final.push_back(Node);
  } while(!Stiva.empty());

  deque<long>::iterator it;
  for(it = Final.begin(); it != Final.end(); ++it)
    fprintf(fout, "%ld ", *it);
  fprintf(fout, "\n");
}

int main()
{
  readData();

  if(!valid())
    fprintf(fout, "-1\n");
  else
    solve();

  fclose(fin);
  fclose(fout);

  return 0;
}