4068 - Grade K
De la Universitas MediaWiki
Cerinţa
Se dă lista muchiilor unui graf neorientat și un nod k
. Să se determine nodurile din graf care au gradul egal cu gradul nodului k
.
Date de intrare
Fişierul de intrare gradekIN.txt
conţine pe prima linie numerele n k
, reprezentând numărul de noduri ale grafului și nodul dat. 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 gradekOUT.txt
va conţine pe prima linie numărul p
de noduri determinate, iar pe linia a doua cele p
noduri determinate, în ordine crescătoare.
Restricţii şi precizări
1 ≤ n ≤ 100
1 ≤ i , j ≤ n
- muchiile se pot repeta în fișierul de intrare
Exemplul 1
gradekIN.txt
5 3 1 4 1 3 3 5 4 5 2 4 1 2 4 2 3 4
gradekOUT.txt
2 1 3
Exemplul 2
gradekIN.txt
5 101 1 4 1 3 3 5 4 5 2 4 1 2 4 2 3 4
gradekOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def verifica_restrictii(n, k, muchii):
# Verificăm restricțiile impuse
if not (1 <= n <= 100):
return False
if not (1 <= k <= n):
return False
for i, j in muchii:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
return True
def noduri_cu_grad_egalcu_k(n, k, muchii):
graf = {}
# Inițializăm dicționarul grafului
for i in range(1, n+1):
graf[i] = set()
# Adăugăm muchiile în graf
for muchie in muchii:
i, j = muchie
graf[i].add(j)
graf[j].add(i)
# Calculăm gradul nodului k
grad_k = len(graf[k])
# Determinăm nodurile cu gradul egal cu gradul nodului k
noduri_egale = [nod for nod, vecini in graf.items() if len(vecini) == grad_k]
return noduri_egale
# Citim datele de intrare
try:
with open("gradekIN.txt", "r") as f:
n, k = map(int, f.readline().split())
muchii = [tuple(map(int, line.split())) for line in f.readlines()]
# Verificăm restricțiile
if not verifica_restrictii(n, k, muchii):
raise ValueError
# Determinăm nodurile cu gradul egal cu gradul nodului k
noduri_rezultat = noduri_cu_grad_egalcu_k(n, k, muchii)
# Scriem rezultatul în fișierul de ieșire
with open("gradekOUT.txt", "w") as f:
if noduri_rezultat:
f.write(str(len(noduri_rezultat)) + "\n")
f.write(" ".join(map(str, noduri_rezultat)))
else:
f.write("Nu există noduri cu gradul egal cu gradul nodului k")
except ValueError:
with open("gradekOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
except Exception as e:
with open("gradekOUT.txt", "w") as f:
f.write("A apărut o eroare în timpul procesării datelor.\n")
f.write(str(e))