Cod sursa(job #2374925)

Utilizator alexconstantinalexandru constantin alexconstantin Data 7 martie 2019 21:18:33
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;
const int nmax=100001;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int grad[nmax],sol[nmax],vc[nmax],n,m,k;
typedef pair<int,int>pereche;
vector<pereche>v[nmax];
bitset<nmax>seen;

bool verif()
{
    for(int i=1;i<=n;i++)
        {
            if(grad[i]%2!=0||grad[i]==0)
            return false;
        }
    return true;
}
int st[nmax],nr;
void euler(int nod)
{
    k++;
    st[k]=nod;
    if(seen[nod]==1)
    {
        while(k!=0&&grad[st[k]]==0)
        {
            nr++;
            sol[nr]=st[k];
            k--;
        }
    }
    else
        seen[nod]=1;
    if(k>0)
    {
        for(int i=0;i<v[st[k]].size();i++)
            if(vc[v[st[k]][i].second]==0)
                {
                    vc[v[st[k]][i].second]=1;
                    grad[v[st[k]][i].first]--;
                    grad[st[k]]--;
                    euler(v[st[k]][i].first);
                }

    }
}
int main()
{
    in>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
        grad[x]++;grad[y]++;

    }
    if(!verif())
        out<<"-1";
    else
    {
        euler(1);
        for(int i=1;i<=nr;i++)
            out<<sol[i]<<" ";
    }
    return 0;
}