Editing 0548 - Hamilton

== Cerința ==
Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.
== Date de intrare ==
Fișierul de intrare hamiltonin.txt conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există muchie de la i la j.
== Date de ieșire ==
Fișierul de ieșire hamiltonout.txt va conține pe prima linie numărul 1, dacă s-a determinat un ciclu hamiltonian, respectiv 0, în caz contrar. Dacă s-a determinat un ciclu hamiltonian, pe linia următoare se vor afișa vârfurile acestui ciclu, separate prin exact un spațiu.
== Restricții și precizări ==
*1 &les; n &les; 10
1 &les; i, j &les; n
*în ciclul afișat, primul și ultimul vârf sunt egale
*orice ciclu hamiltonian afișat va fi acceptat
== Exemplu 1 ==
;hamiltonin.txt
:9
:1 2
;1 4
:2 3
:2 4
:2 5
:3 4
:3 8
:3 9
:4 6
:5 6
:5 7
:5 8
:7 8
:8 9
;hamiltonout.txt
:1
:1 2 3 9 8 7 5 6 4 1
<br>
== Exemplu 2 ==
;hamiltonin.txt
:0
: 0 0
;hamiltonout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0548 - Hamilton
def is_valid(v, pos, path, graph):
    if not graph[path[pos - 1]][v]:
        return False

    if v in path:
        return False

    return True

def hamiltonian_cycle_util(graph, path, pos):
    n = len(graph)

    if pos == n:
        return graph[path[pos - 1]][path[0]] == 1

    for v in range(n):
        if is_valid(v, pos, path, graph):
            path[pos] = v

            if hamiltonian_cycle_util(graph, path, pos + 1):
                return True

            path[pos] = -1

    return False

def hamiltonian_cycle(graph):
    n = len(graph)
    path = [-1] * n

    path[0] = 0

    if not hamiltonian_cycle_util(graph, path, 1):
        return 0, []

    return 1, [v + 1 for v in path] + [path[0] + 1]

def check_restrictions(n, edges):
    if not (1 <= n <= 10):
        return False
    for i, j in edges:
        if not (1 <= i <= n) or not (1 <= j <= n):
            return False
    return True

def write_output_with_restrictions(file_path, result, n, edges):
    with open(file_path, 'w') as file:
        if not check_restrictions(n, edges):
            file.write("Nu au fost respectate cerintele impuse\n")
            return

        file.write(str(result[0]) + '\n')

        if result[0] == 1:
            file.write(' '.join(map(str, result[1])) + '\n')

def read_input(file_path):
    with open(file_path, 'r') as file:
        n = int(file.readline().strip())
        graph = [[0] * n for _ in range(n)]

        for line in file:
            i, j = map(int, line.strip().split())
            graph[i - 1][j - 1] = 1
            graph[j - 1][i - 1] = 1

    return n, graph

if __name__ == "_main_":
    input_file = "hamiltonin.txt"
    output_file = "hamiltonout.txt"

    n, graph = read_input(input_file)
    result = hamiltonian_cycle(graph)
    write_output_with_restrictions(output_file, result, n, [(i + 1, j + 1) for i in range(n) for j in range(n) if graph[i][j] == 1])
</syntaxhighlight>