Cod sursa(job #3198575)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 29 ianuarie 2024 20:01:46
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include<bits/stdc++.h>
using namespace std;
ifstream F("ciclueuler.in");
ofstream G("ciclueuler.out");
int n,m,i,j,k,l=1,t;
vector<int> g[100001],h;
bitset<100001> u;
void B(int i)
{
    u[i]=1;
    for(int j:g[i])
        if(!u[j])
            B(j);
}
void A(int i)
{
    int j,k=g[i].size(),l;
    vector<int>::iterator p,q;
    for(j=0;j<k;++j)
        if(l=g[i][j],p=find(g[i].begin(),g[i].end(),l),q=find(g[l].begin(),g[l].end(),i),p!=g[i].end()&&q!=g[l].end())
           g[i].erase(p),g[l].erase(q),A(l);
    h.push_back(i);
}
int main()
{
    for(F>>n>>m;m--;F>>i>>j,g[i].push_back(j),g[j].push_back(i));
    for(i=1;i<=n;++i)
        if(g[i].size()&1)
            ++k,l=i;
        else if(g[i].size()>0&&!t)
            t=i;
    if(k>2||k==1)
        return G<<-1,0;
    for(B(t),i=1;i<=n&&(u[i]||!g[i].size());++i);
    if(i<=n)
        return G<<-1,0;
    for(A(l),k=h.size()-1,i=0;i<k;G<<h[i++]<<' ');
    return 0;
}