Editing 4073 - Componente Conexe 5 (section)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, m, q, noduri_interes):
    if not (1 <= n <= 1000 and 1 <= m <= n * (n - 1) // 2 and 1 <= q <= 1000):
        return False
    for nod in noduri_interes:
        if not (1 <= nod <= n):
            return False
    return True

def dfs(nod, graf, vizitat, componenta):
    vizitat[nod] = True
    componenta.append(nod)
    for vecin in graf[nod]:
        if not vizitat[vecin]:
            dfs(vecin, graf, vizitat, componenta)

def gaseste_componente_conexe(graf, noduri_interes):
    componente = []
    vizitat = {nod: False for nod in graf}
    for nod in noduri_interes:
        if not vizitat[nod]:
            componenta = []
            dfs(nod, graf, vizitat, componenta)
            componente.append(componenta)
    return componente

def main():
    # Citirea datelor de intrare
    with open("componenteconexe5IN.txt", "r") as fisier:
        try:
            n, m = map(int, fisier.readline().split())
            graf = {i: [] for i in range(1, n + 1)}
            for _ in range(m):
                muchie = list(map(int, fisier.readline().split()))
                if len(muchie) != 2 or not (1 <= muchie[0] <= n and 1 <= muchie[1] <= n):
                    raise ValueError("Datele nu corespund formatului asteptat.")
                graf[muchie[0]].append(muchie[1])
                graf[muchie[1]].append(muchie[0])
            q = int(fisier.readline())
            noduri_interes = list(map(int, fisier.readline().split()))
        except ValueError as e:
            with open("componenteconexe5OUT.txt", "w") as fisier_out:
                fisier_out.write(str(e))
            return

    # Verificarea restricțiilor
    if not verificare_restrictii(n, m, q, noduri_interes):
        with open("componenteconexe5OUT.txt", "w") as fisier_out:
            fisier_out.write("Datele nu corespund restrictiilor impuse")
        return

    # Identificarea componentelor conexe
    componente = gaseste_componente_conexe(graf, set(noduri_interes))

    # Scrierea rezultatelor în fișierul de ieșire
    with open("componenteconexe5OUT.txt", "w") as fisier_out:
        for nod in noduri_interes:
            for componenta in componente:
                if nod in componenta:
                    fisier_out.write(str(len(componenta)) + "\n")
                    break

if __name__ == "__main__":
    main()
</syntaxhighlight>