Simina: Pagină nouă: = 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 sem...

2023-12-12T19:54:42Z

Pagină nouă: = Cerinţa = Se dă un graf neorientat cu <code>n</code> vârfuri și un număr natural <code>k</code>. Să se afișeze vârfurile din graf care au gradul egal cu <code>k</code>. = Date de intrare = Fişierul de intrare <code>gradkIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>k</code>, 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 <code>i j</code>, cu sem...

New page

= Cerinţa =
Se dă un graf neorientat cu <code>n</code> vârfuri și un număr natural <code>k</code>. Să se afișeze vârfurile din graf care au gradul egal cu <code>k</code>.

= Date de intrare =
Fişierul de intrare <code>gradkIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>k</code>, 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 <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>gradkOUT.txt</code> va conţine pe prima linie numărul <code>m</code> de vârfuri cu gradul <code>k</code>, urmat de cele <code>m</code> vârfuri cu gradul <code>k</code>, în ordine crescătoare, separate prin câte un spațiu. Dacă graful nu conține niciun vârf cu gradul egal cu <code>k</code>, atunci se va afișa <code>NU EXISTA</code>.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>0 ≤ k ≤ n</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare

= Exemplul 1 =
<code>gradkIN.txt</code>
5 3
1 4
2 5
2 3
2 1
4 5
3 2
4 3
<code>gradkOUT.txt</code>
2 2 4

== Explicație ==
Vârfurile <code>2</code> și <code>4</code> au gradul egal cu <code>3</code>.

= Exemplul 1 =
<code>gradkIN.txt</code>
5 101
1 4
2 5
2 3
2 1
4 5
3 2
4 3
<code>gradkOUT.txt</code>
Datele corespund restrictiilor impuse

= Rezolvare =
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>

4060 - Grad K - Revision history