Editing 4070 - Subgraf 2

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri, etichetate de la <code>1</code> la <code>n</code>, <code>m</code> muchii și un număr <code>k</code>. Din acest graf se elimină toate nodurile etichetate cu multipli ai lui <code>k</code>. Să se determine câte muchii va avea subgraful obținut.

= Date de intrare =
Programul citește de la tastatură numerele <code>n m k</code>, apoi citește <code>m</code> perechi de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Programul va afișa pe ecran numărul de muchii ale subgrafului obținut.

= Restricţii şi precizări =

* <code>1 < k < n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>

= Exemplul 1 =
Intrare
 5 6 2
 1 5
 2 5
 2 3
 2 4
 4 5
 4 3
Ieșire
 1

= Explicație =
Se elimină vârfurile <code>2 4</code>. Subgraful va conține vârfurile <code>1 3 5</code>, cu o singură muchie.

== Exemplul 2 ==
Intrare
 5 6 1000
Ieșire
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def elimina_muchii_multipli(graf, k):
    muchii_noi = []
    for muchie in graf:
        i, j = muchie
        if i % k != 0 and j % k != 0:
            muchii_noi.append(muchie)
    return muchii_noi

def verificare_restrictii(n, m, k):
    if not (1 < k < n <= 100):
        print("Datele nu corespund restrictiilor impuse")
        return False

    return True

def main():
    # Citirea datelor de intrare pentru n, m și k
    n, m, k = map(int, input().split())

    # Verificarea restricțiilor pentru n, m și k
    if not verificare_restrictii(n, m, k):
        return

    muchii = []
    for _ in range(m):
        # Citirea muchiilor
        muchie = tuple(map(int, input().split()))
        muchii.append(muchie)

    # Eliminarea nodurilor etichetate cu multipli ai lui k
    muchii_noi = elimina_muchii_multipli(muchii, k)

    # Afișarea numărului de muchii ale subgrafului obținut
    print(len(muchii_noi))

if __name__ == "__main__":
    main()

</syntaxhighlight>