0548 - Hamilton: Difference between revisions

From Bitnami MediaWiki
VisualWikitext
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...
 
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Cerința ==
== Cerința ==
Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.
Se dă un graf neorientat cu '''n''' vârfuri. Determinați, dacă există, un ciclu hamiltonian.
== Date de intrare ==
== 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.
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 ==
== 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.
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 ==
== Restricții și precizări ==
*1 ⩽ n ⩽ 10
*'''1 ⩽ n ⩽ 10'''
1 ⩽ i, j ⩽ n
*'''1 ⩽ i, j ⩽ n'''
*în ciclul afișat, primul și ultimul vârf sunt egale
*în ciclul afișat, primul și ultimul vârf sunt egale
*orice ciclu hamiltonian afișat va fi acceptat
*orice ciclu hamiltonian afișat va fi acceptat
== Exemplu 1 ==
== Exemplu 1 ==
;hamiltonin.txt
;'''hamiltonin.txt'''
:9
:9
:1 2
:1 2
Line 27: Line 28:
:7 8
:7 8
:8 9
:8 9
;hamiltonout.txt
;'''hamiltonout.txt'''
:1
:1
:1 2 3 9 8 7 5 6 4 1
:1 2 3 9 8 7 5 6 4 1
<br>
<br>
== Exemplu 2 ==
== Exemplu 2 ==
;hamiltonin.txt
;'''hamiltonin.txt'''
:0
:0
: 0 0
: 0 0
;hamiltonout.txt
;'''hamiltonout.txt'''
: Nu au fost respectate cerintele impuse
: Nu au fost respectate cerintele impuse
<br>
<br>
Line 41: Line 42:
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
#0548 - Hamilton
#0548 - Hamilton
def is_valid(v, pos, path, graph):
def check_constraints(n, a):
     if not graph[path[pos - 1]][v]:
    # 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
         return False


     if v in path:
     # Check constraints 1 ≤ i, j ≤ n
         return False
    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
     return True


def hamiltonian_cycle_util(graph, path, pos):
def backtracking():
     n = len(graph)
     global k
 
     k = 1
     if pos == n:
     while k > 0:
        return graph[path[pos - 1]][path[0]] == 1
         if st[k] < n:
 
             st[k] += 1
     for v in range(n):
             if e_valid():
         if is_valid(v, pos, path, graph):
                 if k == n:
             path[pos] = v
                    afisare()
 
                else:
             if hamiltonian_cycle_util(graph, path, pos + 1):
                    k += 1
                 return True
                    st[k] = 0
 
         else:
            path[pos] = -1
            k -= 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')
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


         if result[0] == 1:
def afisare():
            file.write(' '.join(map(str, result[1])) + '\n')
    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


def read_input(file_path):
with open("hamiltonin.txt", "r") as f:
    with open(file_path, 'r') as file:
    n = int(f.readline().strip())
        n = int(file.readline().strip())
    a = [[0] * (n + 1) for _ in range(n + 1)]
        graph = [[0] * n for _ in range(n)]
    for line in f:
        u, v = map(int, line.strip().split())
        a[u][v] = a[v][u] = 1


        for line in file:
# Check constraints before proceeding with backtracking
            i, j = map(int, line.strip().split())
if not check_constraints(n, a):
            graph[i - 1][j - 1] = 1
    exit()
            graph[j - 1][i - 1] = 1


    return n, graph
ns = 0
st = [0] * 100


if __name__ == "_main_":
with open("hamiltonout.txt", "w") as g:
     input_file = "hamiltonin.txt"
     backtracking()
     output_file = "hamiltonout.txt"
     if ns == 0:
        g.write("0\n")


    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>
</syntaxhighlight>

Latest revision as of 16:52, 8 January 2024

Cerința[edit | edit source]

Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.

Date de intrare[edit | edit source]

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[edit | edit source]

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[edit | edit source]

  • 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[edit | edit source]

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[edit | edit source]

hamiltonin.txt
0
0 0
hamiltonout.txt
Nu au fost respectate cerintele impuse


Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line>

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

</syntaxhighlight>

Retrieved from "http://wiki.universitas.ro/index.php?title=0548_-_Hamilton&oldid=9212"