Simina: Pagină nouă: = Cerința = Dându-se un graf neorientat cu `n` noduri și `m` muchii, să se determine numărul componentelor conexe. = Date de intrare = Fișierul de intrare `nrcompconexe1IN.txt`conține pe prima linie numerele `n` și `m`, iar pe următoarele `m` linii se află câte două numere `i` și `j` cu semnificația că există în graf muchia `(i, j)`. = Date de ieșire = Fișie...

2023-12-13T12:54:23Z

Pagină nouă: = Cerința = Dându-se un graf neorientat cu <code>n</code> noduri și <code>m</code> muchii, să se determine numărul componentelor conexe. = Date de intrare = Fișierul de intrare <code>nrcompconexe1IN.txt</code>conține pe prima linie numerele <code>n</code> și <code>m</code>, iar pe următoarele <code>m</code> linii se află câte două numere <code>i</code> și <code>j</code> cu semnificația că există în graf muchia <code>(i, j)</code>. = Date de ieșire = Fișie...

New page

= Cerința =
Dându-se un graf neorientat cu <code>n</code> noduri și <code>m</code> muchii, să se determine numărul componentelor conexe.

= Date de intrare =
Fișierul de intrare <code>nrcompconexe1IN.txt</code>conține pe prima linie numerele <code>n</code> și <code>m</code>, iar pe următoarele <code>m</code> linii se află câte două numere <code>i</code> și <code>j</code> cu semnificația că există în graf muchia <code>(i, j)</code>.

= Date de ieșire =
Fișierul de ieșire <code>nrcompconexe1OUT.txt</code> va conține pe prima linie un singur număr natural reprezentând numărul componentelor conexe.

= Restricții și precizări =

* <code>3 ≤ n ≤ 30.000</code>
* <code>1 ≤ m ≤ min(n * (n - 1) / 2, 100.000)</code>

= Exemplul 1 =
<code>nrcompconexe1IN.txt</code>
7 5
3 1
4 5
5 6
3 2
1 2
<code>nrcompconexe1OUT.txt</code>
3

=== Explicație ===
Există trei componente conexe, una formată din nodurile <code>1,2,3</code>, a doua formată din <code>4,5,6</code> și ultima componentă conexă formată doar din nodul izolat <code>7</code>.

== Exemplul l ==
<code>nrcompconexe1IN.txt</code>
1 2
<code>nrcompconexe1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, m):
if not (3 <= n <= 30000) or not (1 <= m <= min(n * (n - 1) // 2, 100000)):
with open("nrcompconexe1OUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, vizitat, lista_adiacenta):
vizitat[nod] = True
for vecin in lista_adiacenta[nod]:
if not vizitat[vecin]:
dfs(vecin, vizitat, lista_adiacenta)

def numara_componente_conexe(n, muchii):
lista_adiacenta = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
lista_adiacenta[muchie[0]].append(muchie[1])
lista_adiacenta[muchie[1]].append(muchie[0])

vizitat = {i: False for i in range(1, n + 1)}
componente = 0

for nod in range(1, n + 1):
if not vizitat[nod]:
dfs(nod, vizitat, lista_adiacenta)
componente += 1

return componente

# Citirea datelor de intrare
with open("nrcompconexe1IN.txt", "r") as fisier_intrare:
n, m = map(int, fisier_intrare.readline().split())
muchii = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(m)]

# Verificare restricții
if not verificare_restrictii(n, m):
exit()

# Calculul numărului de componente conexe
rezultat = numara_componente_conexe(n, muchii)

# Scrierea rezultatului în fișierul de ieșire
with open("nrcompconexe1OUT.txt", "w") as fisier_iesire:
fisier_iesire.write(str(rezultat))

</syntaxhighlight>

4282 - Nr Comp Conexe 1 - Revision history