Cod sursa(job #1728841)

Utilizator xSliveSergiu xSlive Data 13 iulie 2016 19:12:38
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <stack>
#define NMAX 100001
#define pb push_back
using namespace std;

void euler(vector<int> *v,int val,vector<int> &sol){
    stack<int> st;
    st.push(val);
    while(!st.empty()){
        int u = st.top();
        if(v[u].size()){
            int el = v[u].back();
            v[u].pop_back();
            v[el].erase(find(v[el].begin(),v[el].end(),u));
            st.push(el);
        }
        else{
            sol.pb(u);
            st.pop();
        }
    }
}

int main()
{
    ifstream f("ciclueuler.in");
    ofstream g("ciclueuler.out");
    int start=1,n,m,a,b;
    vector<int> v[NMAX];
    vector<int> sol;
    int grad[NMAX]={0};
    f >> n >> m;
    for(int i=0;i<m;i++){
        f >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
        grad[a]++;
        grad[b]++;
    }
    for(int i=1;i<=n;i++){
        if(grad[i]%2){
            g << "-1";
            return 0;
        }
        else start = i;
    }
    euler(v,start,sol);
    for(int i=1;i<sol.size();i++)
        g << sol[i] << " ";

    return 0;
}