Simina: Pagină nouă: = 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şie...

2023-12-13T10:36:26Z

Pagină nouă: = 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şie...

New page

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

0438 - Componente Conexe - Revision history