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

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