Simina: Pagină nouă: == Enunț == Se considerã un graf neorientat conex cu `n` vârfuri, numerotate de la `1` la `n`, şi `m` muchii. Definim distanţa minimă între două noduri `x` şi `y` ca fiind numărul minim de muchii al unui lanţ elementar care uneşte `x` cu `y`. = Cerinţa = Sã se determine nodul aflat la cea mai mare distanţã minimă faţã de nodul `1`. = Date de intrare = Fişie...

2023-12-13T15:58:04Z

Pagină nouă: == 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şie...

New page

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

0126 - D Max - Revision history