Cod sursa(job #1895629)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 28 februarie 2017 09:15:42
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define mp make_pair
#define x first
#define y second
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector <pair<int,int> > v[100005];
vector <int> sol;
int i,j,n,m,f[100005],muchii[500005],nr,idx[100005];
///stack <pair<int,int> > st;
void conex(int nod)
{
    if(f[nod])
        return;
    f[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++)
        conex(v[nod][i].x);
    nr++;
}
void go(int nod)
{
    while(idx[nod] < v[nod].size())
    {
        pair<int,int> now = v[nod][ idx[nod] ];
        if(muchii[ now.y ] == 0)
        {
            muchii[ now.y ] = 1;
            go(now.x);
        }
        idx[nod]++;
    }
    sol.push_back(nod);
}
int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        int a,b;
        fin >> a >> b;
        v[a].push_back(mp(b,i));
        v[b].push_back(mp(a,i));
    }
    conex(1);
    if(nr != n)
    {
        cout<<-1;return 0;
    }
    for(i = 1; i <= n; i++)
        if(v[i].size() % 2)
        {
            cout<<-1;return 0;
        }
    go(1);
    for(i = 0; i < sol.size() - 1; i++)
        cout<<sol[i]<<" ";
    return 0;
}