Cod sursa(job #1581257)

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

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

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

inline bool is_euler()
{
    for(int i=1; i<=n; i++)
        if(g[i].size()%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);
    }
    if(!is_euler()) fout << -1;
    else euler(1);
    return 0;
}