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 ⩽ n ⩽ 10
• 1 ⩽ i, j ⩽ 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

Exemplu 2

hamiltonin.txt

0

0 0

hamiltonout.txt

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 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>