Cod sursa(job #1557690)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 27 decembrie 2015 23:31:56
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#define nmax 100004
#include <list>
#include <stack>
#include <queue>

using namespace std;

int N,M;
bool viz[nmax];
int d[nmax];
list <int> G[nmax],R;
stack <int> S;
queue <int> Q;

int main(){

    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    int x,y;
    scanf("%d %d ",&N,&M);
    while(M--){
      scanf("%d %d ",&x,&y);
      G[x].push_back(y);d[x]++;
      G[y].push_back(x);d[y]++;
    }

    Q.push(1);
    viz[1] = true;
    while(!Q.empty()){
      x = Q.front();
      Q.pop();
      for(list <int> :: iterator it = G[x].begin();it != G[x].end();++it)
        if(viz[*it] == false){
          Q.push(*it);
          viz[*it] = true;
        }
    }

    for(x = 1;x <= N;++x)if(d[x]%2 == 1 || viz[x] == false){printf("-1\n");return 0;}

    x = 1;
    do{

      while(!G[x].empty()){
          y = G[x].front();
          G[x].pop_front();
          for(list <int> :: iterator it = G[y].begin();it != G[y].end();++it)
            if(*it == x){
              G[y].erase(it);
              break;
            }

          S.push(x);
          x = y;
        }

      x = S.top();
      S.pop();
      R.push_back(x);
    }while(!S.empty());

    for(list <int> :: iterator it = R.begin();it != R.end();++it)printf("%d ",*it);
    printf("\n");
    return 0;
}