0419 - Subgraf 1

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 pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire subgraf1OUT.txt va conţine pe prima linie numărul M de muchii ale subgrafului obținut.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplul 2

subgraf1IN.txt

5
1 5
2 5
3 5
2 3
4 2

subgraf1OUT.txt

3

Explicație

Se elimină vârfurile 1 4. Subgraful obținut va conține vârfurile 2 3 5, cu 3 muchii.

Exemplul 1

subgraf1IN.txt

101

subgraf1OUT.txt

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>