4282 - Nr Comp Conexe 1

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.txtconț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șierul de ieșire nrcompconexe1OUT.txt va conține pe prima linie un singur număr natural reprezentând numărul componentelor conexe.

Restricții și precizări

• 3 ≤ n ≤ 30.000
• 1 ≤ m ≤ min(n * (n - 1) / 2, 100.000)

Exemplul 1

nrcompconexe1IN.txt

7 5
3 1
4 5
5 6
3 2
1 2

nrcompconexe1OUT.txt

3

Explicație

Există trei componente conexe, una formată din nodurile 1,2,3, a doua formată din 4,5,6 și ultima componentă conexă formată doar din nodul izolat 7.

Exemplul l

nrcompconexe1IN.txt

1 2

nrcompconexe1OUT.txt

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

1. 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)]

1. Verificare restricții

if not verificare_restrictii(n, m):

   exit()

1. Calculul numărului de componente conexe

rezultat = numara_componente_conexe(n, muchii)

1. Scrierea rezultatului în fișierul de ieșire

with open("nrcompconexe1OUT.txt", "w") as fisier_iesire:

   fisier_iesire.write(str(rezultat))

</syntaxhighlight>