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

#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")