Cod sursa(job #2013594)

Utilizator patcasrarespatcas rares danut patcasrares Data 21 august 2017 20:06:13
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<iostream>
#include<vector>
#define DN 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m,a,b,v[5*DN],g[DN],r[5*DN],nr;
vector<pair<int,int> >x[DN];
void dfs(int nod)
{
    for(auto i:x[nod])
        if(!v[i.second])
        {
            m--;
            v[i.second]=1;
            dfs(i.first);
           // return;
        }
    if(m==0)
    {
        nr++;
        r[nr]=nod;
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        g[a]++;
        g[b]++;
        x[a].push_back(make_pair(b,i));
        x[b].push_back(make_pair(a,i));
    }
    for(int i=1;i<=n;i++)
        if(g[i]%2)
        {
            fout<<-1;
            return 0;
        }
    dfs(1);
    if(r[nr]==r[1]&&nr>1)
        nr--;
    for(int i=1;i<=nr;i++)
        fout<<r[i]<<' ';
}