Cod sursa(job #1111447)

Utilizator FayedStratulat Alexandru Fayed Data 18 februarie 2014 21:22:33
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <list>
#include <stack>
#define NMAX 100001
using namespace std;

int n,m,k;
int Sol[NMAX];
bool vizitat[NMAX];
int degree[NMAX];
list < int > Graf[NMAX];
stack < int > S;

void read(){

    int x,y;
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);

      for(register int i=1;i<=m;++i){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        Graf[y].push_back(x);

            ++degree[x];
            ++degree[y];
   }
}

void DFS(int node){

    vizitat[node] = 1;

        for(list < int > ::iterator it = Graf[node].begin(); it!=Graf[node].end();++it)
            if(!vizitat[*it])
                DFS(*it);
}

bool este_eulerian(){

    DFS(1);
    for(register int i=1;i<=n;++i)
        if(!vizitat[i])
            return 0;

    for(register int i=1;i<=n;++i)
        if(degree[i]%2 != 0)
            return 0;
return 1;
}

void sterg(int v,int w){

    --degree[v];
    --degree[w];

    Graf[v].pop_front();

        for(list < int > ::iterator it = Graf[w].begin(); it!= Graf[w].end(); ++it)
            if(*it == v){

                Graf[w].erase(it);

                        break;
            }
}

void euler(int node){


    while(!Graf[node].empty()){

        int w = Graf[node].front();
          S.push(node);
            sterg(node,w);
               node = w;
    }
}

void solve(){

  int node = 1;

   do{

        euler(node);
        node = S.top();
        S.pop();

        Sol[++k] = node;

   }while(!S.empty());
}

void write(){

    if(!este_eulerian())
        printf("-1");

      else{
                solve();
                    for(register int i=k;i>0;--i)
                        printf("%d ",Sol[i]);
      }
}

int main(){

    read();
    write();

return 0;
}