0548 - Hamilton
De la Universitas MediaWiki
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
#0548 - Hamilton
def check_constraints(n, a):
# Check constraints 1 ≤ n ≤ 10
if not (1 <= n <= 10):
with open("hamiltonout.txt", "w") as g:
g.write("Nu au fost respectate cerintele 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("hamiltonout.txt", "w") as g:
g.write("Nu au fost respectate cerintele 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("hamiltonout.txt", "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("hamiltonin.txt", "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
# Check constraints before proceeding with backtracking
if not check_constraints(n, a):
exit()
ns = 0
st = [0] * 100
with open("hamiltonout.txt", "w") as g:
backtracking()
if ns == 0:
g.write("0\n")