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

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