4152 - Lant Maxim 1

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf q. Să se determine cel mai lung lanț elementar cu extremitatea finală în q.

Date de intrare

Fişierul de intrare lantmaxim1IN.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 numărul q.

Date de ieşire

Fişierul de ieşire lantmaxim1OUT.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
• 1 ≤ q ≤ n

Exemplul 1:

lantmaxim1IN.txt

5 6
1 4 
1 3 
3 5 
4 5 
1 2 
3 4
5

lantmaxim1OUT.txt

2 1 3 4 5 

Exemplul 2:

lantmaxim1IN.txt

21 21
1 4 
1 3 
3 5 
4 5 
1 2 
3 4
5

lantmaxim1OUT.txt

Nu corespunde restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n, muchii, q):

   if not (1 <= n <= 20):
       return False
   for u, v in muchii:
       if not (1 <= u <= n) or not (1 <= v <= n):
           return False
   if not (1 <= q <= n):
       return False
   return True

def gestionare_restrictii(file_path_out):

   with open(file_path_out, 'w') as file_out:
       file_out.write("Nu corespunde restrictiilor impuse")
   exit()

def citeste_graf(file_path):

   with open(file_path, 'r') as file:
       n, m = map(int, file.readline().split())
       muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

       try:
           q = int(file.readline())
       except ValueError:
           gestionare_restrictii("lantmaxim1OUT.txt")

   if not verifica_restrictii(n, muchii, q):
       gestionare_restrictii("lantmaxim1OUT.txt")

   return n, muchii, q

def dfs_lant_maxim(q, graf, vizitat, path, lant_maxim):

   vizitat[q] = True
   path.append(q)

   for vecin in graf[q]:
       if not vizitat[vecin]:
           dfs_lant_maxim(vecin, graf, vizitat, path, lant_maxim)

   if len(path) >= len(lant_maxim):
       lant_maxim.clear()
       lant_maxim.extend(path)

   path.pop()
   vizitat[q] = False

def lungime_lant(q, graf, vizitat):

   lant_maxim = []
   dfs_lant_maxim(q, graf, vizitat, [], lant_maxim)
   return len(lant_maxim), lant_maxim

def gaseste_lant_maxim(n, muchii, q):

   graf = {i: [] for i in range(1, n + 1)}
   for u, v in muchii:
       graf[u].append(v)
       graf[v].append(u)

   vizitat = {i: False for i in range(1, n + 1)}

   lungime_maxima = 0
   lant_maxim = []

   for v in range(1, n + 1):
       if not vizitat[v]:
           lungime, lant = lungime_lant(v, graf, vizitat)
           if lungime > lungime_maxima:
               lungime_maxima = lungime
               lant_maxim = lant

   return lant_maxim

def scrie_lant_maxim(file_path, lant_maxim):

   with open(file_path, 'w') as file:
       file.write(' '.join(map(str, lant_maxim)) + '\n')

if __name__ == "__main__":

   file_in = "lantmaxim1IN.txt"
   file_out = "lantmaxim1OUT.txt"

   n, muchii, q = citeste_graf(file_in)
   lant_maxim = gaseste_lant_maxim(n, muchii, q)

   if lant_maxim:
       scrie_lant_maxim(file_out, lant_maxim)
   else:
       with open(file_out, 'w') as file_out:
           file_out.write("Nu corespunde restrictiilor impuse")

</syntaxhighlight>