View source for 4068 - Grade K

= Cerinţa =
Se dă lista muchiilor unui graf neorientat și un nod <code>k</code>. Să se determine nodurile din graf care au gradul egal cu gradul nodului <code>k</code>.

= Date de intrare =
Fişierul de intrare <code>gradekIN.txt</code> conţine pe prima linie numerele <code>n k</code>, reprezentând numărul de noduri ale grafului și nodul dat. 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>gradekOUT.txt</code> va conţine pe prima linie numărul <code>p</code> de noduri determinate, iar pe linia a doua cele <code>p</code> noduri determinate, în ordine crescătoare.

= Restricţii şi precizări =

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

= Exemplul 1 =
<code>gradekIN.txt</code>
 5 3
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4 
<code>gradekOUT.txt</code>
 2
 1 3 

= Exemplul 2 =
<code>gradekIN.txt</code>
 5 101
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4 
<code>gradekOUT.txt</code>
 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

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