4074 - Distante

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ă dintre p și r este egală cu distanța minimă dintre r și q.

Date de intrare

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

Date de ieşire

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

Restricţii şi precizări

• n ≤ 1000

Exemplul 1

distanteIN.txt

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

distanteOUT.txt

3 6 7 

Exemplul 2

distanteIN.txt

1001 86 37 3

distanteOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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()