0437 - Conex

Cerinţa

Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex.

Date de intrare

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

Date de ieşire

Fişierul de ieşire conexOUT.txt va conţine mesajul DA, dacă graful dat este conex, respectiv NU, în caz contrar.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta

Exemplul 1

conexIN.txt

5
1 4 
3 5
2 4

conexOUT.txt

NU

Exemplul 2

conexIN.txt

101

conexOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def respecta_restrictii(n, muchii):

   return 1 <= n <= 100 and all(1 <= i <= n and 1 <= j <= n for i, j in muchii)

def este_conex(n, muchii):

   # Verifică restricțiile
   if not respecta_restrictii(n, muchii):
       return "Datele nu corespund restrictiilor impuse"

   # Restul codului rămâne neschimbat

   lista_adiacenta = {i: set() for i in range(1, n + 1)}
   for muchie in muchii:
       x, y = muchie
       lista_adiacenta[x].add(y)
       lista_adiacenta[y].add(x)

   vizitat = set()

   def dfs(nod):
       vizitat.add(nod)
       for vecin in lista_adiacenta[nod]:
           if vecin not in vizitat:
               dfs(vecin)

   # Folosim DFS pentru a vizita toate nodurile din graf
   dfs(1)

   # Verificăm dacă toate nodurile au fost vizitate
   return "DA" if len(vizitat) == n else "NU"

1. Citirea din fișierul de intrare

with open("conexIN.txt", "r") as fisier:

   n = int(fisier.readline())
   muchii = [tuple(map(int, linie.split())) for linie in fisier]

1. Verifică restricțiile și scrie rezultatul în fișierul de ieșire

with open("conexOUT.txt", "w") as fisier:

   rezultat = este_conex(n, muchii)
   fisier.write(rezultat)

</syntaxhighlight>