Cod sursa(job #871942)

Utilizator FayedStratulat Alexandru Fayed Data 5 februarie 2013 16:31:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
#include <list>
#include <queue>
using namespace std;

 int n,m;
 list < int > Graf[100001];
 vector < int > eulerian;
 stack < int > ST;
 queue < int > q;
 int grad[100001],vizitat[100001];

void citesc(){

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

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

        scanf("%d%d",&xs,&ys);
        Graf[xs].push_back(ys);
        grad[xs]++;
        Graf[ys].push_back(xs);
        grad[ys]++;
    }
fclose(stdin);
}

void BFS(int nod){

    vizitat[nod] = 1;
    q.push(nod);
    int first;
        while(!q.empty()){

            first = q.front();
            q.pop();
            for(list < int > ::iterator it = Graf[first].begin();it!=Graf[first].end();++it)
                    if(!vizitat[*it]){
                        vizitat[*it] = 1;
                        q.push(*it);
                    }
        }
   }

int conex(){

    BFS(1);
    for(int k=2;k<=n;k++)
        if(vizitat[k] == 0)
            return 0;
return 1;
}

int is_eulerian(){

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

void sterg(int v, int w){

    grad[v]--; grad[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 v){

    while(true){

        if(Graf[v].empty())
            break;

            int w = Graf[v].front();
                ST.push(v);
             sterg(v,w);
             v=w;
        }
}

int solve(){

    int v = is_eulerian();
    if(!v)
        return -1;
    do{
        euler(v);
        v = ST.top();
        ST.pop();
        eulerian.push_back(v);
    }while(!ST.empty());
return 1;
}

void afisez(int ok){

    if(ok == -1)
    printf("-1\n");
    else
        for(vector < int > ::iterator it = eulerian.begin();it!=eulerian.end();++it)
            printf("%d ", *it);
}

int main(){

citesc();

afisez(solve());
fclose(stdout);
return 0;
}