View source for 4073 - Componente Conexe 5

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și <code>m</code> muchii și un șir de <code>q</code> noduri. Să se determine pentru fiecare nod <code>x</code> din șir numărul de noduri din componenta conexă din care face parte <code>x</code>.

= Date de intrare =
Fişierul de intrare <code>componenteconexe5IN.txt</code> conține pe prima linie numerele <code>n m</code>, reprezentând numărul de noduri și numărul de muchii ale grafului. Fiecare dintre următoarele <code>m</code> 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>.

Următoarea linie conține numărul <code>q</code>, iar ultima linie a fișierului de intrare conține un șir de <code>q</code> noduri, seprate prin câte un spațiu.

= Date de ieşire =
Fişierul de ieşire <code>componenteconexe5OUT.txt</code> va conține <code>q</code> linii; fiecare linie va conține numărul de noduri din componenta conexă a nodului corespunzător din șir.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 1000</code>
* <code>1 ≤ i , j ≤ n</code>
* <code>1 ≤ q ≤ 1000</code>
* <code>1 ≤ x ≤ n</code>

= Exemplul 1 =
<code>componenteconexe5IN.txt</code>
 5 3
 1 2
 3 5
 2 4
 3
 2 5 1
<code>componenteconexe5OUT.txt</code>
 3
 2
 3

= Exemplul 2 =
<code>componenteconexe5IN.txt</code>
 1001 1001
<code>componenteconexe5OUT.txt</code>
 Datele nu corespund restrictiilor impuse

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