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

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