Cod sursa(job #1226598)

Utilizator TudorMTudor Moldovanu TudorM Data 6 septembrie 2014 13:17:11
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n, m, d[200001],ciclu[200001],nr;
vector <int> v[200001];
void citire()
{
    int i, j, x, y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        d[x]++;
        d[y]++;
    }
}
int vecini(int x, int &w)
{
    int i,j;
    for(i=0;i<v[x].size();i++)
    {
        if(v[x][i]!=0)
        {
            w=v[x][i];
            v[x][i]=0;
            for(j=0;j<v[w].size();j++)
            {
                if(v[w][j]==x)
                {
                    v[w][j]=0;
                    break;
                }
            }
            return 1;
        }
    }
    return 0;
}
void euler(int x)
{
    int i, w;
    while(vecini(x,w))
    {
        euler(w);
    }
    ciclu[++nr]=x;
}
int main()
{
    citire();
    int i, ok1=1;
    for(i=1;i<=n&&ok1;i++)if(d[i]%2)ok1=0;
    if(!ok1)g<<-1;
    else
    {
        euler(1);
        for(i=1;i<nr;i++)g<<ciclu[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}