Cod sursa(job #777262)

Utilizator ion824Ion Ureche ion824 Data 11 august 2012 18:09:32
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
#define pb push_back
using namespace std;
vector<int> a[100002],L;
vector<int>::iterator it;
int deg[100002],N,M;
bool viz[100002];
queue<int> Q;
stack<int> s;

void bfs(){
     int v;
     Q.push(1); viz[1]=1;
     while(!Q.empty()){
            v=Q.front(); Q.pop();
            for(it=a[v].begin();it!=a[v].end();++it)
              if(!viz[*it])
                Q.push(*it),viz[*it]=1;                               
                       }          
     }

bool conex(){
     bfs();
     for(int i=2;i<=N;++i)
       if(!viz[i])return 0;
     return 1;
     }
     
void sterge(int v,int w){
     deg[v]--; deg[w]--;
     a[v].erase(a[v].begin());
     for(it=a[w].begin();it!=a[w].end();++it)
        if(*it==v)
          {
           a[w].erase(it);
           break;
          }    
     }

void euler(int v){
     while(1)
     {
     if(a[v].empty())break;
     int w=*a[v].begin();
     s.push(v);  
     sterge(v,w);
     v=w;
     }               
}

int main(void){
    ifstream fin("ciclueuler.in");
    ofstream fout("ciclueuler.out");
    int i,x,y,v;
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
     fin>>x>>y;
     a[x].pb(y); deg[x]++;
     a[y].pb(x); deg[y]++;                 
    }
    if(conex==0){ fout<<"-1\n"; return 0; }
    for(i=1;i<=N;++i)if(deg[i]&1){ fout<<"-1\n"; return 0; }
    v=1;
    do{
      euler(v);
      v=s.top(); s.pop();                               
      L.pb(v);                             
    }while(!s.empty());
    for(it=L.end()-1;it!=L.begin()-1;--it)fout<<*it<<' ';
 return 0;   
}