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 check_constraints(n, a):

   # Check constraints 1 ≤ n ≤ 10
   if not (1 <= n <= 10):
       with open("hamilton.out", "w") as g:
           g.write("Datele nu corespund restrictiilor impuse\n")
       return False

   # Check constraints 1 ≤ i, j ≤ n
   for i in range(1, n + 1):
       for j in range(1, n + 1):
           if not (0 <= a[i][j] <= 1):  # Corrected condition here
               with open("hamilton.out", "w") as g:
                   g.write("Datele nu corespund restrictiilor impuse\n")
               return False

   return True

def backtracking():

   global k
   k = 1
   while k > 0:
       if st[k] < n:
           st[k] += 1
           if e_valid():
               if k == n:
                   afisare()
               else:
                   k += 1
                   st[k] = 0
       else:
           k -= 1

def e_valid():

   global k
   if k > 1:
       if not a[st[k - 1]][st[k]]:
           return 0
       else:
           for i in range(1, k):
               if st[i] == st[k]:
                   return 0
   if k == n:
       if not a[st[1]][st[k]]:
           return 0
   return 1

def afisare():

   global k, ns
   with open("hamilton.out", "a") as g:
       g.write("1\n")
       g.write(" ".join(map(str, st[1:n + 1])) + " " + str(st[1]) + "\n")
   k = 0
   ns += 1

with open("hamilton.in", "r") as f:

   n = int(f.readline().strip())
   a = [[0] * (n + 1) for _ in range(n + 1)]
   for line in f:
       u, v = map(int, line.strip().split())
       a[u][v] = a[v][u] = 1

1. Check constraints before proceeding with backtracking

if not check_constraints(n, a):

   exit()

ns = 0 st = [0] * 100

with open("hamilton.out", "w") as g:

   backtracking()
   if ns == 0:
       g.write("0\n")

</syntaxhighlight>