4060 - Grad K

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

<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>