Cod sursa(job #2038725)

Utilizator tanasaradutanasaradu tanasaradu Data 13 octombrie 2017 22:41:00
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
const int MMAX=500005;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int st[MMAX],dr[MMAX],n,m,k,sol[MMAX];
vector<int>L[MMAX];
bool viz[MMAX];
int ind[MMAX];
inline void Read()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>st[i]>>dr[i];
        int x=st[i],y=dr[i];
        L[x].push_back(i);
        L[y].push_back(i);
    }
}
inline bool Check()
{
    for(int i=1;i<=n;i++)
    {
        int lug=L[i].size();
        if(lug%2)
            return false;
    }
    return true;
}
void DFS(int nod)
{
    int lug=L[nod].size();
    while(ind[nod]<lug)
    {
        int x=L[nod][ind[nod]];
        ind[nod]++;
        if(!viz[x])
        {
            viz[x]=1;
            DFS(st[x]+dr[x]-nod);
        }
    }
    ++k;
    sol[k]=nod;
}
int main()
{
    Read();
    bool ok=Check();
    if(!ok)
        fout<<"-1\n";
    else
    {
        DFS(1);
        for(int i=1;i<k;i++)
            fout<<sol[i]<<" ";
        fout<<"\n";
    }
    fin.close();
    fout.close();
    fin.close();
    fout.close();
    return 0;
}