0538 - Lungime Minima

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și vârf p . Să se determine toate nodurile q ale grafului cu proprietatea că lungimea minimă a unui lanț de la q la p este L.

Date de intrare

Fişierul de intrare lungimeminimaIN.txt conţine pe prima linie numerele n p L, cu semnificația precizată. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire lungimeminimaOUT.txt va conţine pe prima linie numărul de vârfuri determinate. A doua linie va conține în ordine crescătoare vârfurile determinate, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta;
• pentru toate datele de test există cel puțin un vârf q cu proprietatea dorită;

Exemplul 1

lungimeminimaIN.txt

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

lungimeminimaOUT.txt

3
2 3 6

Exemplul 2

lungimeminimaIN.txt

101 101 101

lungimeminimaOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> from collections import deque

def gaseste_noduri_cu_lungime_minima(graf, n, p, L):

   vizitat = [False] * (n + 1)
   noduri_rezultat = []

   def bfs(nod, lungime_tinta):
       coada = deque([(nod, 0)])
       vizitat[nod] = True  # Setăm nodul de pornire ca vizitat

       while coada:
           nod_curent, lungime_curenta = coada.popleft()

           if lungime_curenta == lungime_tinta:
               noduri_rezultat.append(nod_curent)

           for vecin in graf[nod_curent]:
               if not vizitat[vecin]:
                   vizitat[vecin] = True
                   coada.append((vecin, lungime_curenta + 1))

   bfs(p, L)

   return noduri_rezultat

def verificare_restrictii(n, i, j):

   if not (1 <= n <= 100):
       return False
   if not (1 <= i <= n) or not (1 <= j <= n):
       return False
   return True

def main():

   with open("lungimeminimaIN.txt", "r") as fisier_intrare:
       n, p, L = map(int, fisier_intrare.readline().split())

       # Verificare restricții
       if not verificare_restrictii(n, p, L):
           with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
               fisier_iesire.write("Datele nu corespund restrictiilor impuse")
           return

       graf = {i: [] for i in range(1, n + 1)}

       for _ in range(n):
           muchie = tuple(map(int, fisier_intrare.readline().split()))
           if not verificare_restrictii(n, muchie[0], muchie[1]):
               with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
                   fisier_iesire.write("Datele nu corespund restrictiilor impuse")
               return
           graf[muchie[0]].append(muchie[1])
           graf[muchie[1]].append(muchie[0])

   noduri_rezultat = gaseste_noduri_cu_lungime_minima(graf, n, p, L)

   with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
       fisier_iesire.write(str(len(noduri_rezultat)) + "\n")
       fisier_iesire.write(" ".join(map(str, sorted(noduri_rezultat))))

if __name__ == "__main__":

   main()

</syntaxhighlight>