Cod sursa(job #750077)

Utilizator memaxMaxim Smith memax Data 20 mai 2012 15:12:30
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main(){
    ifstream cinr ("ciclueuler.in");
    ofstream cour ("ciclueuler.out");
    int n,m,a,b,y,z;
    cinr >> n; cinr >> m;
    vector< vector<int> > g(n+1);
    vector<int> p(n+1,0);
    bool t;
    for(int i=1; i<=m; i++){
            cinr >> a;
            cinr >> b;
            g[a].push_back(b);
            g[b].push_back(a);
            p[a]++;
            p[b]++;
            }
    for(int i=1; i<=n; i++){
            if(p[i]%2){
                       cour << "-1";
                       return 0;
                       }
            }
    vector<int> q,r;
    q.push_back(1);
    while(!q.empty()){
                      y=q.back();
                      if(g[y].empty()){
                                       r.push_back(y);
                                       q.pop_back();
                                       }
                      else             {
                                       z=g[y].back();
                                       g[y].pop_back();
                                       for(int i=0; i<g[z].size(); i++){
                                               if(g[z][i]==y){
                                                              g[z][i]=g[z].back();
                                                              g[z].pop_back();
                                                              break;
                                                              }
                                               }
                                       q.push_back(z);
                                       }
                      }
    for(int i=1; i<r.size(); i++){ cour << r[i-1] << " "; }
    cinr.close(); cour.close();
    //cin.ignore(2);
    return 0;
    }