Cod sursa(job #1218949)

Utilizator rangerChihai Mihai ranger Data 12 august 2014 23:28:18
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
const int nmax  = 100010;
vector<int> g[nmax];
vector<int>::iterator it;
int n,m,i,x,y,used[nmax];

void dfs(int v)
{
    used[v]=1;
    for (int i=0;i<g[v].size();i++)
        if (!used[g[v][i]])
        dfs(g[v][i]);
}
bool conex()
{
    dfs(1);
    for (int i=1;i<=n;i++)
        if (!used[i]) return false;
    return  true;
}
bool eulerian()
{
    for (int i=1;i<=n;i++)
        if (g[i].size()&1) return false;
    return conex();
}
void solve(int v,int aux=0)
{
    while (true) {
        if (g[v].empty())
            break;
        int to = g[v][g[v].size()-1];
        g[v].pop_back();
        g[to].erase( find( g[to].begin(), g[to].end(), v) );
        solve(to,aux+1);
    }
    if (aux)
    cout<<v<<" ";
}
int main()
{
    cin>>n>>m;
    for (;m--;) {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    if (!eulerian()) {
        cout<<"-1";
        return 0;
    }
   solve(1);
    return 0;
}