Cod sursa(job #239782)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 5 ianuarie 2009 20:33:41
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
const int NMAX=100001;
int N,M,deg[NMAX];
vector<int> Adj[NMAX],sol;
queue<int> Q;
bitset<NMAX> u;
void bf(int vf){
     int x;
     vector<int>::iterator it;
     Q.push(vf);
     u[vf]=1;
     while (!Q.empty()){
       x=Q.front();Q.pop();
       for (it=Adj[x].begin();it!=Adj[x].end();++it)
        if (!u[*it]) u[*it]=1,Q.push(*it);
       }
     }
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
void sterge(int x,int vf){
     Adj[vf].pop_back();
     vector<int>::iterator it;
     for (it=Adj[x].begin();it!=Adj[x].end();++it)
       if (*it==vf){
         Adj[x].erase(it);
         break;}
     }
stack<int> S;
void euler(){
     int vf,x;
     S.push(1);
     while (!S.empty()){
       vf=S.top();
       if (Adj[vf].empty()){
         sol.push_back(vf);
         S.pop();
         continue;}
       x=Adj[vf].back();
       sterge(x,vf);
       S.push(x);}
     }      
int main(){
    int i,j;
    fin>>N>>M;
    while (M--){
      fin>>i>>j;
      Adj[i].push_back(j);
      Adj[j].push_back(i);
      ++deg[i];++deg[j];}
    
    bool ok=true;
    bf(1);
    for (i=1;i<=N && ok;++i)
     if (!u[i] || deg[i]&1) 
       ok=false;
    if (!ok){
     fout<<"-1\n";
     return 0;}
    
    euler();
    sol.pop_back();
    vector<int>::iterator it;
    for (it=sol.begin();it!=sol.end();++it)
     fout<<*it<<' ';
    return 0;
}