Cod sursa(job #1581218)

Utilizator tudormaximTudor Maxim tudormaxim Data 26 ianuarie 2016 17:43:57
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");

const int nmax = 100005;
vector <int> g[nmax];
int n, m, x[nmax], y[nmax], gr[nmax];
bool viz[nmax];

inline bool is_euler()
{
    for(int i=1; i<=n; i++)
        if(gr[i]%2==1) return false;
    return true;
}

void euler(int dad)
{
    int i, son;
    for(i=0; i<g[dad].size(); i++)
    {
        son=g[dad][i];
        if(viz[son]==false)
        {
            viz[son]=true;
            euler(x[son]+y[son]-dad);
        }
    }
    fout << dad << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    int i;
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x[i] >> y[i];
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
        gr[x[i]]++;
        gr[y[i]]++;
    }
    if(!is_euler()) fout << -1;
    else euler(1);
    return 0;
}