Cod sursa(job #1423755)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 22 aprilie 2015 16:26:24
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 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,stiva;
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;
      
     stiva.push(nod);
     while(stiva.size())
          {
           nod=stiva.top(); 
           if(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();
                              
                             stiva.push(vecin);
                            }
           else{
                st.push(nod);
                stiva.pop();
               }
          }
}
 
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;
}