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

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