4073 - Componente Conexe 5

Cerinţa

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

Date de intrare

Fişierul de intrare componenteconexe5IN.txt conține pe prima linie numerele n m, reprezentând numărul de noduri și numărul de muchii ale grafului. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

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

Date de ieşire

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

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• 1 ≤ i , j ≤ n
• 1 ≤ q ≤ 1000
• 1 ≤ x ≤ n

Exemplul 1

componenteconexe5IN.txt

5 3
1 2
3 5
2 4
3
2 5 1

componenteconexe5OUT.txt

3
2
3

Exemplul 2

componenteconexe5IN.txt

1001 1001

componenteconexe5OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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()