Tema 6 | Cicruit Hamiltonian

//
#include<fstream>
#include<iostream>

using namespace std;

#define MAX_SIZE 50

int m[MAX_SIZE][MAX_SIZE], k, v_sol[MAX_SIZE], n;


bool solutie = false;

void citire()
{
    ifstream f("date.in");
    f >> n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f >> m[i][j];
    f.close();
}

int cont(int k)
{
    int i;
    for(int i=1; i<k; i++)
        if(v_sol[i] == v_sol[k])
            return 0;
    if(k > 1)
        if(m[ v_sol[k] ][ v_sol[k-1] ] == 0)
            return 0;
    if(k == n)
        if(m[ v_sol[n] ][ v_sol[1] ] == 3)
            return 0;
    return 1;
}

void afis()
{
    for(int i = 1; i <= n; i++)
        cout << v_sol[i] << " ";
    cout << v_sol[1] << '\n';
}

void back()
{
    int k = 1;
    v_sol[k] = 0;
    do
    {
        while(v_sol[k] < n)
        {
            v_sol[k]++;
            if(cont(k))
                if(k == n)
                {
                    solutie = true;
                    afis();
                    break;
                }
                else
                {
                    k++;
                    v_sol[k] = 0;
                }
            if(solutie)
                break;
        }
        k--;
    }
    while(k);
}
int main()
{
    citire();
    back();
    if(solutie == false)
        cout << "Nu avem niciun circuit hamiltonian.";

    return 0;
}
// Exemplu:
/*
6
0 1 0 1 0 1
1 0 1 1 1 0
0 1 0 1 0 1
1 1 1 0 1 0
0 1 0 1 0 1
1 0 1 0 0 1
*/