Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri, etichetate de la `1` la `n`. Din acest graf se elimină toate vârfurile care au gradul minim. Să se determine câte muchii va avea subgraful obținut. = Date de intrare = Fişierul de intrare `subgraf1IN.txt` conţine pe prima linie numărul `n`, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o p...

2023-12-12T22:29:08Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. Din acest graf se elimină toate vârfurile care au gradul minim. Să se determine câte muchii va avea subgraful obținut. = Date de intrare = Fişierul de intrare <code>subgraf1IN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o p...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. Din acest graf se elimină toate vârfurile care au gradul minim. Să se determine câte muchii va avea subgraful obținut.

= Date de intrare =
Fişierul de intrare <code>subgraf1IN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. 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>subgraf1OUT.txt</code> va conţine pe prima linie numărul <code>M</code> de muchii ale subgrafului obținut.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare

= Exemplul 2 =
<code>subgraf1IN.txt</code>
5
1 5
2 5
3 5
2 3
4 2
<code>subgraf1OUT.txt</code>
3

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

== Exemplul 1 ==
<code>subgraf1IN.txt</code>
101
<code>subgraf1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_graf(fisier):
with open(fisier, 'r') as file:
n = int(file.readline().strip())
muchii = [tuple(map(int, linie.strip().split())) for linie in file]

return n, muchii

def scrie_iesire(fisier, numar_muchii):
with open(fisier, 'w') as file:
file.write(str(numar_muchii))

def verifica_restricții(n, muchii):
# Verifică restricția 1: 1 ≤ n ≤ 100
if not (1 <= n <= 100):
raise ValueError("Datele nu corespund restrictiilor impuse")

# Verifică restricția 2: 1 ≤ i, j ≤ n pentru fiecare muchie
if not all(1 <= i <= n and 1 <= j <= n for i, j in muchii):
raise ValueError("Datele nu corespund restrictiilor impuse")

def construieste_graf(n, muchii):
graf = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])
return graf

def gaseste_varfurile_cu_grad_minim(graf):
grade = {v: len(adiacenti) for v, adiacenti in graf.items()}
grad_minim = min(grade.values())
varfuri_grad_minim = [v for v, grad in grade.items() if grad == grad_minim]
return varfuri_grad_minim

def elimina_varfurile_cu_grad_minim(graf, varfuri_grad_minim):
for v in varfuri_grad_minim:
del graf[v]
for u, adiacenti in graf.items():
graf[u] = [w for w in adiacenti if w != v]
return graf

def main():
fisier_intrare = 'subgraf1IN.txt'
fisier_iesire = 'subgraf1OUT.txt'

try:
n, muchii = citeste_graf(fisier_intrare)

# Adaugă verificarea restricțiilor
verifica_restricții(n, muchii)

graf = construieste_graf(n, muchii)

varfuri_grad_minim = gaseste_varfurile_cu_grad_minim(graf)
graf_nou = elimina_varfurile_cu_grad_minim(graf.copy(), varfuri_grad_minim)

numar_muchii = sum(len(adiacenti) for adiacenti in graf_nou.values()) // 2
scrie_iesire(fisier_iesire, numar_muchii)

except ValueError as e:
with open(fisier_iesire, 'w') as file:
file.write(str(e))

if __name__ == "__main__":
main()

</syntaxhighlight>

0419 - Subgraf 1 - Revision history