0417 - Grad Max

Cerinţa

Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile de grad maxim.

Date de intrare

Fişierul de intrare gradmaxIN.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 gradmaxOUT.txt va conţine pe prima linie numărul m de vârfuri de grad maxim, urmat de cele m vârfuri de grad maxim ,în ordine crescătoare, separate prin exact un spațiu.

Restricţii şi precizări

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

Exemplul 1

gradmaxIN.txt

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

gradmaxOUT.txt

2 2 4

Exemplul 2

gradmaxIN.txt

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

gradmaxOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def citeste_graf(file_path):

   with open(file_path, 'r') as file:
       n = int(file.readline().strip())

       # Verifica restricțiile pentru numărul de vârfuri
       if not (1 <= n <= 100):
           return None, None, "Datele nu corespund restrictiilor impuse"

       muchii = [tuple(map(int, line.strip().split())) for line in file]

       # Verifica restricțiile pentru vârfurile muchiilor
       for i, j in muchii:
           if not (1 <= i <= n) or not (1 <= j <= n):
               return None, None, "Datele nu corespund restrictiilor impuse"

   return n, muchii, None

def calculeaza_grad(n, muchii):

   grad = [0] * (n + 1)
   for i, j in muchii:
       grad[i] += 1
       grad[j] += 1
   return grad

def vafuri_grad_maxim(grad):

   max_grad = max(grad)
   vafuri_maxime = [i for i, val in enumerate(grad) if val == max_grad]
   return vafuri_maxime

def scrie_output(file_path, vafuri_maxime, eroare=None):

   with open(file_path, 'w') as file:
       if eroare:
           file.write(eroare)
       else:
           file.write(f"{len(vafuri_maxime)}\n")
           file.write(" ".join(map(str, vafuri_maxime)))

if __name__ == "__main__":

   file_input = "gradmaxIN.txt"
   file_output = "gradmaxOUT.txt"

   n, muchii, eroare = citeste_graf(file_input)

   scrie_output(file_output, [], eroare) if eroare else None

   if not eroare:
       grad = calculeaza_grad(n, muchii)
       vafuri_maxime = vafuri_grad_maxim(grad)
       scrie_output(file_output, vafuri_maxime)

</syntaxhighlight>