View source for 0438 - Componente Conexe

= Cerinţa =
Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.

= Date de intrare =
Fişierul de intrare <code>componenteconexeIN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>componenteconexeOUT.txt</code> va conţine pe prima linie numărul de componente conexe <code>nrc</code>. Fiecare dintre următoarele <code>nrc</code> linii va conține în ordine crescătoare, separate printr-un spațiu, vârfurile din componenta conexă curentă.

Ordinea de afișare a componentelor conexe va fi cea crescătoare a vârfului cu eticheta minimă din fiecare componentă.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* în fișierul de intrare muchiile se pot repeta

= Exemplul 1 =
<code>componenteconexeIN.txt</code>
 5
 1 4 
 3 5
 2 4
<code>componenteconexeOUT.txt</code>
 2
 1 2 4
 3 5

= Exemplul 2 =
<code>componenteconexeIN.txt</code>
 101
<code>componenteconexeOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def DFS(nod, vizitat, componenta, lista_adiacenta):
    vizitat[nod] = True
    componenta.append(nod)

    for vecin in lista_adiacenta[nod]:
        if not vizitat[vecin]:
            DFS(vecin, vizitat, componenta, lista_adiacenta)

def gaseste_componente_conexe(n, muchii):
    lista_adiacenta = {i: [] for i in range(1, n + 1)}

    for muchie in muchii:
        i, j = muchie
        lista_adiacenta[i].append(j)
        lista_adiacenta[j].append(i)

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

    for nod in range(1, n + 1):
        if not vizitat[nod]:
            componenta = []
            DFS(nod, vizitat, componenta, lista_adiacenta)
            componente.append(sorted(componenta))

    return componente

def verificare_restrictii(n, muchii):
    if not (1 <= n <= 100):
        return False

    for i, j in muchii:
        if not (1 <= i <= n) or not (1 <= j <= n):
            return False

    return True

def main():
    with open("componenteconexeIN.txt", "r") as fisier:
        n = int(fisier.readline().strip())
        muchii = [list(map(int, linie.strip().split())) for linie in fisier]

    if not verificare_restrictii(n, muchii):
        with open("componenteconexeOUT.txt", "w") as fisier:
            fisier.write("Datele nu corespund restrictiilor impuse")
        return

    componente = gaseste_componente_conexe(n, muchii)

    with open("componenteconexeOUT.txt", "w") as fisier:
        fisier.write(f"{len(componente)}\n")
        for comp in componente:
            fisier.write(" ".join(map(str, comp)) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>