0538 - Lungime Minima

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și vârf p . Să se determine toate nodurile q ale grafului cu proprietatea că lungimea minimă a unui lanț de la q la p este L.

Date de intrare

Fişierul de intrare lungimeminimaIN.txt conţine pe prima linie numerele n p L, cu semnificația precizată. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire lungimeminimaOUT.txt va conţine pe prima linie numărul de vârfuri determinate. A doua linie va conține în ordine crescătoare vârfurile determinate, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta;
• pentru toate datele de test există cel puțin un vârf q cu proprietatea dorită;

Exemplul 1

lungimeminimaIN.txt

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

lungimeminimaOUT.txt

3
2 3 6

Exemplul 2

lungimeminimaIN.txt

101 101 101

lungimeminimaOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from collections import deque

def gaseste_noduri_cu_lungime_minima(graf, n, p, L):
    vizitat = [False] * (n + 1)
    noduri_rezultat = []

    def bfs(nod, lungime_tinta):
        coada = deque([(nod, 0)])
        vizitat[nod] = True  # Setăm nodul de pornire ca vizitat

        while coada:
            nod_curent, lungime_curenta = coada.popleft()

            if lungime_curenta == lungime_tinta:
                noduri_rezultat.append(nod_curent)

            for vecin in graf[nod_curent]:
                if not vizitat[vecin]:
                    vizitat[vecin] = True
                    coada.append((vecin, lungime_curenta + 1))

    bfs(p, L)

    return noduri_rezultat

def verificare_restrictii(n, i, j):
    if not (1 <= n <= 100):
        return False
    if not (1 <= i <= n) or not (1 <= j <= n):
        return False
    return True

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

        # Verificare restricții
        if not verificare_restrictii(n, p, L):
            with open("lungimeminimaOUT.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(n):
            muchie = tuple(map(int, fisier_intrare.readline().split()))
            if not verificare_restrictii(n, muchie[0], muchie[1]):
                with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
                    fisier_iesire.write("Datele nu corespund restrictiilor impuse")
                return
            graf[muchie[0]].append(muchie[1])
            graf[muchie[1]].append(muchie[0])

    noduri_rezultat = gaseste_noduri_cu_lungime_minima(graf, n, p, L)

    with open("lungimeminimaOUT.txt", "w") as fisier_iesire:
        fisier_iesire.write(str(len(noduri_rezultat)) + "\n")
        fisier_iesire.write(" ".join(map(str, sorted(noduri_rezultat))))

if __name__ == "__main__":
    main()