Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine cel mai lung lanț elementar cu extremitățile p și q.

Date de intrare

Fişierul de intrare lantmaximIN.txt conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Următoarea linie conține două numere p q.

Date de ieşire

Fişierul de ieşire lantmaximOUT.txt va conține cel mai lung lanț elementar cu extremitățile p și q, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricţii şi precizări

1 ≤ n ≤ 20
1 ≤ i , j ≤n
muchiile se pot repeta în fișierul de intrare
1 ≤ p , q ≤ n
pentru toate datele de test, va exista cel puțin un lanț cu extremitățile p q

Exemplul 1:

lantmaximIN.txt

lantmaximOUT.txt

2 1 3 4 5

Exemplul 2:

lantmaximIN.txt

lantmaximOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def citeste_graf(filename):

   with open(filename, 'r') as file:
       try:
           n, m = map(int, file.readline().split())
           graf = {}
           muchii = []
           for _ in range(m):
               i, j = map(int, file.readline().split())
               muchii.append((i, j))
               if i not in graf:
                   graf[i] = []
               if j not in graf:
                   graf[j] = []
               graf[i].append(j)
               graf[j].append(i)
           p, q = map(int, file.readline().split())
       except ValueError:
           return None, None, None, None, None, None

   return n, m, muchii, graf, p, q

def verifica_restrictii(n, m, muchii, p, q):

   if not (1 <= n <= 20):
       return False
   for i, j in muchii:
       if not (1 <= i <= n) or not (1 <= j <= n):
           return False
   if not (1 <= p <= n) or not (1 <= q <= n):
       return False
   return True

def dfs(graf, start, end, path, visited, results):

   visited[start] = True
   path.append(start)

   if start == end:
       results.append(path.copy())

   for neighbor in graf[start]:
       if not visited[neighbor]:
           dfs(graf, neighbor, end, path, visited, results)

   path.pop()
   visited[start] = False

def lanț_maxim(filename_in, filename_out):

   n, m, muchii, graf, p, q = citeste_graf(filename_in)
   
   if n is None:
       with open(filename_out, 'w') as file:
           file.write("Datele nu corespund restrictiilor impuse")
       return

   if not verifica_restrictii(n, m, muchii, p, q):
       with open(filename_out, 'w') as file:
           file.write("Datele nu corespund restrictiilor impuse")
       return

   visited = {v: False for v in graf}
   results = []

   dfs(graf, p, q, [], visited, results)

   if results:
       results.sort()
       result = results[0]

       with open(filename_out, 'w') as file:
           file.write(' '.join(map(str, result)))
   else:
       with open(filename_out, 'w') as file:
           file.write("Nu există lanț între vârfurile date")

Apelul funcției pentru datele din fișierul de intrare lantmaximIN.txt și scrierea rezultatului în lantmaximOUT.txt

lanț_maxim("lantmaximIN.txt", "lantmaximOUT.txt")

</syntaxhighlight>