Simina: Pagină nouă: == Enunț == Se consideră un graf neorientat conex cu `n` noduri, numerotate de la `1` la `n`, şi `m` muchii. Definim distanţa minimă dintre două noduri `x` şi `y` ca fiind numărul minim de muchii al unui lanţ elementar care uneşte `x` cu `y`. = Cerinţa = Se dă o pereche de noduri `p q`. Determinați nodurile `r` cu proprietatea că distanța minimă dintr...

2023-12-13T16:17:26Z

Pagină nouă: == Enunț == Se consideră un graf neorientat conex cu <code>n</code> noduri, numerotate de la <code>1</code> la <code>n</code>, şi <code>m</code> muchii. Definim distanţa minimă dintre două noduri <code>x</code> şi <code>y</code> ca fiind numărul minim de muchii al unui lanţ elementar care uneşte <code>x</code> cu <code>y</code>. = Cerinţa = Se dă o pereche de noduri <code>p q</code>. Determinați nodurile <code>r</code> cu proprietatea că distanța minimă dintr...

New page

== Enunț ==
Se consideră un graf neorientat conex cu <code>n</code> noduri, numerotate de la <code>1</code> la <code>n</code>, şi <code>m</code> muchii. Definim distanţa minimă dintre două noduri <code>x</code> şi <code>y</code> ca fiind numărul minim de muchii al unui lanţ elementar care uneşte <code>x</code> cu <code>y</code>.

= Cerinţa =
Se dă o pereche de noduri <code>p q</code>. Determinați nodurile <code>r</code> cu proprietatea că distanța minimă dintre <code>p</code> și <code>r</code> este egală cu distanța minimă dintre <code>r</code> și <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>distanteIN.txt</code> conţine pe prima linie numere <code>n m p q</code>. Fiecare dintre următoarele <code>m</code> linii va conţine câte două numere <code>x</code> şi <code>y</code>, separate printr-un spaţiu, cu semnificaţia: există o muchie între nodul <code>x</code> şi nodul <code>y</code>.

= Date de ieşire =
Fişierul de ieşire <code>distanteOUT.txt</code> va conține pe prime linie, separate prin câte un spațiu, modurile cerute în ordine crescătoare.

= Restricţii şi precizări =

* <code>n ≤ 1000</code>

= Exemplul 1 =
<code>distanteIN.txt</code>
7 8 2 4
1 2
2 3
2 6
3 4
3 6
3 7
4 5
4 6
<code>distanteOUT.txt</code>
3 6 7

= Exemplul 2 =
<code>distanteIN.txt</code>
1001 86 37 3
<code>distanteOUT.txt</code>
Datele nu corespund restrictiilor impuse

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

def bfs(graf, start):
distante = {nod: float('inf') for nod in graf}
distante[start] = 0
coada = deque([start])

while coada:
nod_curent = coada.popleft()

for vecin in graf[nod_curent]:
if distante[vecin] == float('inf'):
distante[vecin] = distante[nod_curent] + 1
coada.append(vecin)

return distante

def gaseste_noduri_potrivite(graf, p, q):
distante_p = bfs(graf, p)
distante_q = bfs(graf, q)

noduri_potrivite = []
for nod in graf:
if distante_p[nod] == distante_q[nod]:
noduri_potrivite.append(nod)

return noduri_potrivite

def main():
with open("distanteIN.txt", "r") as fisier_intrare:
n, m, p, q = map(int, fisier_intrare.readline().split())

if n > 1000:
with open("distanteOUT.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(m):
x, y = map(int, fisier_intrare.readline().split())
graf[x].append(y)
graf[y].append(x)

noduri_potrivite = gaseste_noduri_potrivite(graf, p, q)

with open("distanteOUT.txt", "w") as fisier_iesire:
if n <= 1000:
fisier_iesire.write(" ".join(map(str, noduri_potrivite)))
else:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()

</syntaxhighlight>

4074 - Distante - Revision history