1622 - Elicoptere

Cerința

Într-un ținut montan, elicopterele sunt folosite pentru a transporta provizii între diferite baze de operațiuni. Aceste baze sunt reprezentate prin nodurile unui graf neorientat, iar zborurile directe între baze sunt reprezentate prin muchiile acestui graf. Se dorește să se determine dacă există o cale între două baze date.

Date de intrare

Programul citește de la tastatură:

Un număr întreg n reprezentând numărul de baze (noduri). Un număr întreg m reprezentând numărul de zboruri directe (muchii). O listă de m perechi de numere întregi, fiecare pereche reprezentând o muchie între două baze. O pereche de numere întregi x și y reprezentând cele două baze între care se dorește verificarea existenței unei căi.

Date de ieșire

Pe ecran se va afișa mesajul "Da" dacă există o cale între baza x și baza y sau "Nu" în caz contrar.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• 1 ⩽ m ⩽ 1000
• 1 ⩽ x,y ⩽ n

Exemplu 1

Intrare

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

Iesire

Da

Exemplu 2

Intrare

5
3
1 2
2 3
3 4
1 5

Iesire

Nu

Rezolvare

<syntaxhighlight lang="python" line> from collections import defaultdict, deque

def citeste_date():

   try:
       n = int(input("Introduceți numărul de baze (n): "))
       m = int(input("Introduceți numărul de zboruri directe (m): "))
       muchii = []
       for _ in range(m):
           u, v = map(int, input().strip().split())
           muchii.append((u, v))
       x, y = map(int, input("Introduceți cele două baze între care se dorește verificarea existenței unei căi (x y): ").split())
       return n, m, muchii, x, y
   except ValueError:
       return None, None, None, None, None

def construieste_graf(n, muchii):

   graf = defaultdict(list)
   for u, v in muchii:
       graf[u].append(v)
       graf[v].append(u)
   return graf

def exista_cale(graf, start, end):

   vizitat = set()
   coada = deque([start])
   while coada:
       nod = coada.popleft()
       if nod == end:
           return True
       for vecin in graf[nod]:
           if vecin not in vizitat:
               vizitat.add(vecin)
               coada.append(vecin)
   return False

def main():

   n, m, muchii, x, y = citeste_date()
   
   if n is None or m is None or muchii is None or x is None or y is None:
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   graf = construieste_graf(n, muchii)
   if exista_cale(graf, x, y):
       print("Da")
   else:
       print("Nu")

if __name__ == "__main__":

   main()

</syntaxhighlight>