Editing 4060 - Grad K

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