Cod sursa(job #778961)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 16 august 2012 13:24:18
Problema Ciclu hamiltonian de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <stack>
#include <vector>
#include <list>

#define MAX 1505

using namespace std;

short n, grad[MAX], nodes[MAX][MAX];
stack<int> S;
vector<int> L;

void init()
{
    for(int i = 1; i <= n; i++)
    {
        grad[i] = n;
        nodes[i][0] = 1;
        for(int j = 1; j <= n; j++)
            nodes[i][j] = 1;
    }
}

void sterge(int v, int w)
{
    grad[v]--; grad[w]--;
    if(v == w)
        grad[w]++;
    nodes[v][w] = 0;
    if(nodes[v][0] == w && grad[v])
        while(!nodes[v][nodes[v][0]]) nodes[v][0]++;
    nodes[w][v] = 0;
    if(nodes[w][0] == v && grad[w])
        while(!nodes[w][nodes[w][0]]) nodes[w][0]++;
}

void euler(int nod)
{
    while(grad[nod])
    {
        int v = nodes[nod][0];
        S.push(nod);
        sterge(nod, v);
        nod = v;
    }
}

int main()
{
    ifstream in("domino2.in"); in>>n; in.close();
    ofstream out("domino2.out");
    if(n % 2)
    {
        if(n == 1)
        {
            out<<"1 1";
            return 0;
        }
        init();
        int v = 1;
        do
        {
            euler(v);
            v = S.top(); S.pop();
            L.push_back(v);
        }while(!S.empty());
        out<<n<<" ";
        for(int i = 1; i < L.size(); i++)
            out<<L[i]<<"\n"<<L[i]<<" ";
        out<<n;
    }
    else
    {
        if(n == 2)
            out<<"1 1\n1 2\n2 2";
        else
            out<<"-1";
    }
    out.close();
    return 0;
}