4060 - Grad K
De la Universitas MediaWiki
Cerinţa
Se dă un graf neorientat cu n
vârfuri și un număr natural k
. Să se afișeze vârfurile din graf care au gradul egal cu k
.
Date de intrare
Fişierul de intrare gradkIN.txt
conţine pe prima linie numerele n
și k
, reprezentând numărul de vârfuri ale grafului, respectiv gradul cerut. 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 gradkOUT.txt
va conţine pe prima linie numărul m
de vârfuri cu gradul k
, urmat de cele m
vârfuri cu gradul k
, în ordine crescătoare, separate prin câte un spațiu. Dacă graful nu conține niciun vârf cu gradul egal cu k
, atunci se va afișa NU EXISTA
.
Restricţii şi precizări
1 ≤ n ≤ 100
0 ≤ k ≤ n
1 ≤ i , j ≤ n
- muchiile se pot repeta în fișierul de intrare
Exemplul 1
gradkIN.txt
5 3 1 4 2 5 2 3 2 1 4 5 3 2 4 3
gradkOUT.txt
2 2 4
Explicație
Vârfurile 2
și 4
au gradul egal cu 3
.
Exemplul 1
gradkIN.txt
5 101 1 4 2 5 2 3 2 1 4 5 3 2 4 3
gradkOUT.txt
Datele corespund restrictiilor impuse
Rezolvare
def citeste_graf(file_path):
with open(file_path, 'r') as file:
n, k = map(int, file.readline().split())
graf = [set() for _ in range(n + 1)]
for line in file:
i, j = map(int, line.split())
graf[i].add(j)
graf[j].add(i)
return n, k, graf
def are_gradul_k(v, k, graf):
return len(graf[v]) == k
def gaseste_vrfuri_cu_grad_k(n, k, graf):
vrfuri_cu_grad_k = [v for v in range(1, n + 1) if are_gradul_k(v, k, graf)]
return vrfuri_cu_grad_k
def respecta_restrictii(n, k, graf):
# Restricție: 1 ≤ n ≤ 100
if not (1 <= n <= 100):
return False
# Restricție: 0 ≤ k ≤ n
if not (0 <= k <= n):
return False
# Restricție: 1 ≤ i, j ≤ n
for i in range(1, n + 1):
if not all(1 <= j <= n for j in graf[i]):
return False
return True
def main():
file_input = "gradkIN.txt"
file_output = "gradkOUT.txt"
n, k, graf = citeste_graf(file_input)
with open(file_output, 'w') as file:
if not respecta_restrictii(n, k, graf):
file.write("Datele nu corespund restrictiilor impuse\n")
else:
vrfuri_cu_grad_k = gaseste_vrfuri_cu_grad_k(n, k, graf)
if vrfuri_cu_grad_k:
file.write(str(len(vrfuri_cu_grad_k)) + ' ')
file.write(' '.join(map(str, vrfuri_cu_grad_k)) + '\n')
else:
file.write("NU EXISTA\n")
if __name__ == "__main__":
main()