0417 - Grad Max
De la Universitas MediaWiki
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
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)