4068 - Grade K

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

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

1. 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))

</syntaxhighlight>