4070 - Subgraf 2 - Revision history

Simina: Pagină nouă: = 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 2023-12-12T22:17:16Z Pagină nouă: = 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... New page = 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>