Cod sursa(job #1880239)

Utilizator Bot32King Max Bot32 Data 15 februarie 2017 17:15:39
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 100001
#define pb push_back

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n , m, x ,y ;
vector < int > G[MAXN];
int grad[MAXN];
int uz[MAXN];
stack < int > st;
vector < int > sol;
void dfs ( int i )
{
    uz[i] = 1;
    for ( vector < int > ::iterator j = G[i].begin(); j != G[i].end(); j++ )
    {
        if ( !uz[(*j) ] )
            dfs((*j));
    }
}

void afis()
{
    for (int i = 0; i < sol.size()-1;  i++ )
        g << sol[i] << " " ;
}

void euler ( int i )
{
    st.push(i);
    while ( !st.empty() )
    {
        int nod = st.top();
        if ( G[nod].size() )
        {
            int vecin = G[nod].back();
            G[nod].pop_back();
            G[vecin].erase(find(G[vecin].begin(), G[vecin].end(), nod) ) ;
            st.push(vecin);
        }
        else
        {
            st.pop();
            sol.push_back(nod);
        }
    }
    afis();
}


int main()
{
    f >> n >> m;
    for ( ; m-- ; )
    {
        f >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
        grad[x]++;
        grad[y]++;
    }
    dfs(1);
    for (int i = 1; i <= n ; i++ )
        if ( !uz[i] or grad[i]%2 == 1 )
        {
            g << -1;
            return 0;
        }
    euler(1);
    return 0;
}