Editing 4074 - Distante

== 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>