Editing 1604 - D Min

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

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

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

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

= Restricţii şi precizări =

* <code>n ≤ 100</code>
* <code>k ≤ 100</code>
* pentru toate perechile <code>x y</code> există cel puțin un drum elementar de la <code>x</code> la <code>y</code>.

= Exemplul 1 =
<code>dminIN.txt</code>
 6 7
 1 3
 1 2
 2 3
 2 4
 3 4
 4 5
 5 6
 3
 1 6
 5 3
 2 5
<code>dminOUT.txt</code>
 4
 2
 2

= Exemplul 2 =
<code>dminIN.txt</code>
 101 101
<code>dminOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>