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 componenteconexeIN.txt conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire componenteconexeOUT.txt va conţine pe prima linie numărul de componente conexe nrc. Fiecare dintre următoarele nrc 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

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta

Exemplul 1

componenteconexeIN.txt

5
1 4 
3 5
2 4

componenteconexeOUT.txt

2
1 2 4
3 5

Exemplul 2

componenteconexeIN.txt

101

componenteconexeOUT.txt

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>