Vizualizare sursă pentru „0126 - D Max”

== 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ă între 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 =
Sã se determine nodul aflat la cea mai mare distanţã minimă faţã de nodul <code>1</code>.

= Date de intrare =
Fişierul de intrare <code>dmaxIN.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>.

= Date de ieşire =
Fişierul de ieşire <code>dmaxOUT.txt</code> va conţine pe prima linie numărul <code>z</code>, prin care este identificat nodul aflat la cea mai mare distanţã minimă faţã de nodul <code>1</code>.

= Restricţii şi precizări =

* <code>0 < n < 100</code>
* <code>0 < m < 1000</code>
* Dacă există mai multe noduri aflate la distanţa maximă, poate fi ales oricare dintre ele.

= Exemplul 1 =
<code>dmaxIN.txt</code>
 6 7
 1 3
 1 2
 2 3
 2 4
 3 4
 4 5
 5 6
<code>dmaxOUT.txt</code>
 6

= Explicație =
Nodul <code>6</code> se află la distanţa minimă <code>4</code> faţă de nodul <code>1</code>.

== Exemplul 2 ==
<code>dmaxIN.txt</code>
 101 1001
<code>dmaxOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def dijkstra(graf, start):
    n = len(graf)
    distante = [float('inf')] * n
    distante[start - 1] = 0

    heap = [(0, start)]

    while heap:
        distanta_curenta, nod_curent = heapq.heappop(heap)

        if distanta_curenta > distante[nod_curent - 1]:
            continue

        for vecin in graf[nod_curent]:
            distanta = distanta_curenta + 1
            if distanta < distante[vecin - 1]:
                distante[vecin - 1] = distanta
                heapq.heappush(heap, (distanta, vecin))

    return distante

def verificare_restrictii(n, m):
    if 0 < n < 100 and 0 < m < 1000:
        return True
    return False

def main():
    with open("dmaxIN.txt", "r") as fisier:
        n, m = map(int, fisier.readline().split())

        if not verificare_restrictii(n, m):
            with open("dmaxOUT.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.readline().split())
            graf[x].append(y)
            graf[y].append(x)

    distante = dijkstra(graf, 1)
    nod_max_distanta = max(range(1, n + 1), key=lambda x: distante[x - 1])

    with open("dmaxOUT.txt", "w") as fisier_iesire:
        fisier_iesire.write(str(nod_max_distanta))

if __name__ == "__main__":
    main()

</syntaxhighlight>