Cod sursa(job #1418850)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 14 aprilie 2015 11:14:52
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");

const int MAX_N = 100005;
const int MAX_M = 500005;

vector <int> a[MAX_N];
stack <int> st;
int i,n,m,x,y;
bool viz[MAX_N];

void dfs(int nod){
     viz[nod]=1;
     for(unsigned int j=0;j<a[nod].size();j++)
       if(!viz[a[nod][j]]) dfs(a[nod][j]);
}

bool eulerian(){
     int i;
     for(i=1;i<=n;i++) viz[i]=0;
     
     dfs(1);
     
     for(i=1;i<=n;i++)
       if(!viz[i] || a[i].size()&1) return false;
       
     return true;
}

void euler(int nod){
     unsigned int j;
     int vecin;
     
     while(a[nod].size()){
                          vecin=a[nod].back();
                          a[nod].pop_back();
                          
                          for(j=a[vecin].size()-1;j>=0 && a[vecin][j]!=nod;j--);
                          a[vecin][j]=a[vecin].back();
                          a[vecin].pop_back();
                          
                          euler(vecin);
                         }
     st.push(nod);
}

int main(){
    fi>>n>>m;
    for(i=1;i<=m;i++){
                      fi>>x>>y;
                      a[x].push_back(y);
                      a[y].push_back(x);
                     }
    
    if(!eulerian()) fo<<"-1\n";
    else{
         euler(1);
         while(st.size()>1){
                            fo<<st.top()<<" ";
                            st.pop();
                           }
        }
    
    fi.close();
    fo.close();
    return 0;
}