Editing 4276 - Nr Comp Conexe

= 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>nrcompconexeIN.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>nrcompconexeOUT.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 ≤ 100</code>
* <code>1 ≤ m ≤ n * (n - 1) / 2</code>

= Exemplul 1 =
<code>nrcompconexeIN.txt</code>
 7 5
 3 1
 4 5
 5 6
 3 2
 1 2
<code>nrcompconexeOUT.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 1 ==
<code>nrcompconexeIN.txt</code>
 101 67
<code>nrcompconexeOUT.txt</code>
 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

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

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

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

</syntaxhighlight>