Cod sursa(job #660982)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 13 ianuarie 2012 16:08:42
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

const int maxN=100010;
const int maxM=500010;

pair<int,int> muchii[maxM];
vector<int> G[maxN];
vector<int> sol;

bool viz[maxM];
int P[maxN];

int n,m;

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

void read()
{
    int i,j,x,y;

    in>>n>>m;

    for(i=1;i<=m;++i)
    {
        in>>x>>y;
        muchii[i]=make_pair(x,y);
        G[x].push_back(i);
        G[y].push_back(i);
    }

}

bool verif()
{
    bool v=true; int i;

    for(i=1;i<=n;++i)
        if(P[i]%2!=0)
        {
            v=false;
            break;
        }

    return v;
}

inline void df(int nod)
{
    while(P[nod]<G[nod].size())
    {
        int mu=G[nod][P[nod]];
        if(viz[mu])
        {
            P[nod]++;
            continue;
        }
        viz[mu]=true;
        int vec=muchii[mu].first+muchii[mu].second-nod;
        P[nod]++;
        df(vec);
        sol.push_back(vec);
    }
}

int main()
{

    read();
    if(verif()==true)
    {
        df(1);
        if(sol.size()!=m)
        {
            out<<-1<<"\n";
            return 0;
        }
		out<<1;
        for(int i=1;i<sol.size();++i)
            out<<" "<<sol[i];
		out<<"\n";
    }
    else out<<-1<<"\n";

    return 0;
}