Editing 0441 - Componente Conexe 1 (section)

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