0548 - Hamilton

From Bitnami MediaWiki
Revision as of 13:13, 31 December 2023 by Ramona Dragoș (talk | contribs) (Pagină nouă: == 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...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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>