Cod sursa(job #1778388)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 13 octombrie 2016 19:03:19
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("domino.in");
ofstream fout("domino.out");

struct date
{
    int f,s,nr;
};

vector <date> v[10];
int ans1[51000];
int ans2[51000];
date st[51000];
int z,m,k;
int viz[10];

void df(int x)
{
    viz[x]=1;
    for(int i=0; i<v[x].size(); ++i)
        if(viz[v[x][i].f]==0)
            df(v[x][i].f);
}

inline void sterge(int x,int y)
{
    for(int i=0; i<v[x].size(); ++i)
        if(v[x][i].nr==y)
        {
            swap(v[x][i],v[x][v[x].size()-1]);
            v[x].pop_back();
            return;
        }
}

void euler()
{
    while(k!=0)
    {
        if(v[st[k].f].size())
        {
            st[k+1]=v[st[k].f][v[st[k].f].size()-1];
            v[st[k].f].pop_back();
            sterge(st[k+1].f,st[k+1].nr);
            ++k;
        }
        else
        {
            ++z;
            ans1[z]=st[k].nr;
            ans2[z]=st[k].s;
            --k;
        }
    }
}

int main()
{
    fin>>m;
    date x;
    int a,b,i;
    for(i=1; i<=m; ++i)
    {
        fin>>a>>b;
        x.f=b;
        x.s=0;
        x.nr=i;
        v[a].push_back(x);
        x.f=a;
        x.s=1;
        v[b].push_back(x);
    }
    int n=10;
    int nr=0;
    int prim=-1,ultim;
    for(i=0; i<n; ++i)
    {
        if(v[i].size()%2==1)
        {
            if(prim==-1)
                prim=i;
            else
                ultim=i;
            ++nr;
        }
        else if(v[i].size()>0 && prim==-1)
            prim=i;
    }
    int ok=1;
    df(prim);
    for(i=0; i<n; ++i)
        if(viz[i]==0 && v[i].size()>0)
            ok=0;


    if((nr!=0 && nr!=2) || ok==0)
        fout<<'0';
    else
    {
        k=1;
        st[k].f=prim;

        if(nr==2)
        {
            date x;
            x.f=ultim;
            x.nr=m+1;
            v[prim].push_back(x);
            x.f=prim;
            v[ultim].push_back(x);
        }

        euler();
        fout<<1<<'\n';
        if(nr==2)
            --z;
        for(i=z-1; i>0; --i)
            fout<<ans1[i]<<' '<<ans2[i]<<'\n';
    }
}