Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii. = Date de intrare = Fişierul de intrare `componenteconexe1IN.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...

2023-12-13T10:48:04Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii. = Date de intrare = Fişierul de intrare <code>componenteconexe1IN.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...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii.

= Date de intrare =
Fişierul de intrare <code>componenteconexe1IN.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>componenteconexe1OUT.txt</code> va conţine pe prima linie numărul <code>NR</code> de muchii ce trebuie adăugate. Fiecare dintre următoarele <code>NR</code> linii va conține câte o muchie <code>x y</code>, care trebuie adăugată pentru ca graful să devină conex.

= 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>componenteconexe1IN.txt</code>
5
1 4
3 5
2 4
<code>componenteconexe1OUT.txt</code>
1
1 3

= Exemplul 2 =
<code>componenteconexe1IN.txt</code>
101
<code>componenteconexe1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def gaseste_componente_conexe(n, muchii):
componente_conexe = []

def gaseste_componenta(v):
for componenta in componente_conexe:
if v in componenta:
return componenta
return None

for muchie in muchii:
i, j = muchie
componente_i = gaseste_componenta(i)
componente_j = gaseste_componenta(j)

if componente_i is not None and componente_j is not None:
if componente_i != componente_j:
componente_i.update(componente_j)
componente_conexe.remove(componente_j)
elif componente_i is not None:
componente_i.add(j)
elif componente_j is not None:
componente_j.add(i)
else:
componente_conexe.append({i, j})

return componente_conexe

def determina_muchii_aditionale(n, muchii):
componente_conexe = gaseste_componente_conexe(n, muchii)

nr_muchii_aditionale = len(componente_conexe) - 1
muchii_aditionale = []

for i in range(len(componente_conexe) - 1):
muchie = (min(componente_conexe[i]), min(componente_conexe[i + 1]))
muchii_aditionale.append(muchie)

return nr_muchii_aditionale, muchii_aditionale

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("componenteconexe1IN.txt", "r") as file_in:
n = int(file_in.readline().strip())
muchii = [tuple(map(int, line.split())) for line in file_in.readlines()]

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

nr_muchii_aditionale, muchii_aditionale = determina_muchii_aditionale(n, muchii)

with open("componenteconexe1OUT.txt", "w") as file_out:
file_out.write(str(nr_muchii_aditionale) + "\n")
for muchie in muchii_aditionale:
file_out.write(f"{muchie[0]} {muchie[1]}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0441 - Componente Conexe 1 - Revision history