Benzar Ioan at 02:22, 3 June 2024

2024-06-03T02:22:42Z

Benzar Ioan: Pagină nouă: == 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 nu...

2024-06-02T19:51:15Z

Pagină nouă: == 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 nu...

New page

== 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 &les; '''n''' &les; 100
*1 &les; '''m''' &les; 1000
*1 &les; '''x,y''' &les; 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>

1622 - Elicoptere - Revision history

Benzar Ioan at 02:22, 3 June 2024