0479 - Lant Maxim

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

5 7
1 4 
1 3 
3 5 
4 5 
1 2 
4 2 
3 4
2 5

lantmaximOUT.txt

2 1 3 4 5 

Exemplul 2:

lantmaximIN.txt

100 100
1 4 
1 3 
3 5 
4 5 
1 2 
4 2 
3 4
2 5

lantmaximOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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

   try:
       with open(filename, 'r') as file:
           n, m = map(int, file.readline().split())
           graf = {}
           muchii = []
           for _ in range(m):
               i, j = map(int, file.readline().split())
               muchii.append((i, j))
               graf.setdefault(i, []).append(j)
               graf.setdefault(j, []).append(i)
           p, q = map(int, file.readline().split())
       return n, m, muchii, graf, p, q
   except ValueError:
       return None, None, None, None, None, None
   except FileNotFoundError:
       print(f"Fisierul {filename} nu a fost gasit.")
       return None, None, None, None, None, None
   except Exception as e:
       print(f"A aparut o eroare la citirea fisierului {filename}: {e}")
       return None, None, None, None, None, None

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

def main():

   try:
       # Get input and output filenames from the user
       input_filename = input("Introduceți numele fișierului de intrare: ")
       output_filename = input("Introduceți numele fișierului de ieșire: ")

       # Call the lanț_maxim function with the provided filenames
       lanț_maxim(input_filename, output_filename)

       print(f"Rezultatele au fost scrise în {output_filename}")
   except Exception as e:
       print(f"A apărut o eroare: {e}")

if __name__ == "__main__":

   main()

</syntaxhighlight>