4276 - Nr Comp Conexe

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 nrcompconexeIN.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șierul de ieșire nrcompconexeOUT.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 ≤ 100
• 1 ≤ m ≤ n * (n - 1) / 2

Exemplul 1

nrcompconexeIN.txt

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

nrcompconexeOUT.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 1

nrcompconexeIN.txt

101 67

nrcompconexeOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n, m):

   if not (3 <= n <= 100 and 1 <= m <= n * (n - 1) / 2):
       with open("nrcompconexeOUT.txt", "w") as fisier_out:
           fisier_out.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 numar_componente_conexe(n, m, muchii):

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

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

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

   return numar_conexe

1. Citirea datelor de intrare

with open("nrcompconexeIN.txt", "r") as fisier:

   n, m = map(int, fisier.readline().split())
   if not verifica_restrictii(n, m):
       exit()
   muchii = [tuple(map(int, fisier.readline().split())) for _ in range(m)]

1. Calculul numărului de componente conexe

rezultat = numar_componente_conexe(n, m, muchii)

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

with open("nrcompconexeOUT.txt", "w") as fisier_out:

   fisier_out.write(str(rezultat))

</syntaxhighlight>