4070 - Subgraf 2
De la Universitas MediaWiki
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
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()