4070 - Subgraf 2

Cerinţa

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

Date de intrare

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

Date de ieşire

Programul va afișa pe ecran numărul de muchii ale subgrafului obținut.

Restricţii şi precizări

• 1 < k < n ≤ 100
• 1 ≤ i , j ≤ n

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 2 4. Subgraful va conține vârfurile 1 3 5, 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>