Cod sursa(job #1694924)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 26 aprilie 2016 11:56:49
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("domino.in");
ofstream g("domino.out");
int N;
vector <int> G[15],Sol;
vector <int> Edge[15][15];
bool Use[50005];
int Stack[100005];
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
        Edge[x][y].push_back(i);
        Edge[y][x].push_back(-i);
    }
}

void Cycle(int node)
{
    while(G[node].size()>0)
    {
        int neighb=*(prev(G[node].end()));
        Stack[++Stack[0]]=node;
        G[node].erase(prev(G[node].end()));
        for(auto it=G[neighb].begin();it!=G[node].end();it++)
            if(*it==node)
            {
                G[neighb].erase(it);
                break;
            }
        node=neighb;
    }
}
inline int mod(int x)
{
    return max(x,-x);
}
void Solve()
{
    int node;
    for(int i=0;i<=9;i++)
        if(G[i].size()>0)
        {
            node=i;
            break;
        }
    do
    {
        Cycle(node);
        node=Stack[Stack[0]];
        Sol.push_back(node);
        --Stack[0];
    } while(Stack[0]>0);
}

void PrintSolution()
{
    for(int i=0;i<Sol.size()-1;i++)
    {
        for(int j=0;j<Edge[Sol[i]][Sol[i+1]].size();j++)
        {
            int e=Edge[Sol[i]][Sol[i+1]][j];
            if(Use[mod(e)]==1)
                continue;
            Use[mod(e)]=1;
            if(e<0)
                g<<-e<<" "<<1<<"\n";
            else
                g<<e<<" "<<0<<"\n";
        }
    }
}
int main()
{
    Read();
    for(int i=0;i<=9;i++)
        if(G[i].size()%2==1)
        {
            g<<"0\n";
            return 0;
        }
    g<<"1\n";
    Solve();
    PrintSolution();
    return 0;
}