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