1604 - D Min

Enunț

Se consideră un graf neorientat conex cu n vârfuri, 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 dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța minimă dintre x și y.

Date de intrare

Fişierul de intrare dminIN.txt conţine pe prima linie două numere n şi m, reprezentând numărul de noduri, respectiv numărul de muchii. 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.

Următoarea linie conține un număr k, iar următoarele k linii câte două numere x y.

Date de ieşire

Fişierul de ieşire dminOUT.txt va conţine k linii. Fiecare linie va conține distanța minimă dintre nodurile x y din fișierul de intrare, în ordinea din fișierul de intrare.

Restricţii şi precizări

• n ≤ 100
• k ≤ 100
• pentru toate perechile x y există cel puțin un drum elementar de la x la y.

Exemplul 1

dminIN.txt

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

dminOUT.txt

4
2
2

Exemplul 2

dminIN.txt

101 101

dminOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verificare_restrictii(n, k):
    if n > 100 or k > 100:
        return False
    return True

def bfs(GRAF, start, sfarsit):
    vizitate = set()
    coada = [[start]]

    if start == sfarsit:
        return 0

    while coada:
        drum = coada.pop(0)
        nod = drum[-1]

        if nod not in vizitate:
            vecini = GRAF[nod]
            for vecin in vecini:
                drum_nou = list(drum)
                drum_nou.append(vecin)
                coada.append(drum_nou)

                if vecin == sfarsit:
                    return len(drum_nou) - 1

            vizitate.add(nod)

    return -1  # Dacă nu există drum între noduri

def main():
    with open('dminIN.txt', 'r') as fisier_intrare:
        n, m = map(int, fisier_intrare.readline().split())

        if not verificare_restrictii(n, m):
            with open('dminOUT.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)

        k = int(fisier_intrare.readline())
        interogari = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(k)]

    with open('dminOUT.txt', 'w') as fisier_iesire:
        for interogare in interogari:
            x, y = interogare
            distanta = bfs(GRAF, x, y)
            fisier_iesire.write(str(distanta) + '\n')

if __name__ == "__main__":
    main()