0475 - Lant

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine toate lanțurile elementare cu extremitățile p și q.

Date de intrare

Fişierul de intrare lantIN.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 lantOUT.txt va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în p, respectiv q, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.Î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

Exemplul 1:

lantIN.txt

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2 5

lantOUT.txt

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

Exemplul 2:

lantIN.txt

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

lantOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n, muchii, p, 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 <= p <= n) or not (1 <= q <= n):
       return False
   return True

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:
           p, q = map(int, file.readline().split())
       except ValueError:
           with open("lantOUT.txt", 'w') as file_out:
               file_out.write("Datele nu corespund restrictiilor impuse")
           exit()

   if not verifica_restrictii(n, muchii, p, q):
       with open("lantOUT.txt", 'w') as file_out:
           file_out.write("Datele nu corespund restrictiilor impuse")
       exit()

   return n, muchii, p, q

def dfs(v, tinta, graf, vizitat, path, rezultat):

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

   if v == tinta:
       rezultat.append(path.copy())
   else:
       for vecin in graf[v]:
           if not vizitat[vecin]:
               dfs(vecin, tinta, graf, vizitat, path, rezultat)

   path.pop()
   vizitat[v] = False

def gaseste_lanturi(n, muchii, p, 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)}
   rezultat = []

   dfs(p, q, graf, vizitat, [], rezultat)

   rezultat = list(set(tuple(lant) for lant in rezultat))
   rezultat.sort()

   return rezultat

def scrie_lanturi(file_path, lanturi):

   with open(file_path, 'w') as file:
       for lant in lanturi:
           file.write(' '.join(map(str, lant)) + '\n')

if __name__ == "__main__":

   file_in = "lantIN.txt"
   file_out = "lantOUT.txt"

   n, muchii, p, q = citeste_graf(file_in)
   rezultat = gaseste_lanturi(n, muchii, p, q)
   scrie_lanturi(file_out, rezultat)

</syntaxhighlight>