Editing 0441 - Componente Conexe 1

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