0473 - Bipartit Complet

Cerinţa

Se consideră două mulţimi nevide A şi B, cu proprietatea că formează o partiție a mulțimii {1,2,...,n}. Să se construiască un graf bipartit complet cu n vârfuri, bipartit peste partiţia formată din mulțimile A și B.

Date de intrare

Fişierul de intrare bipartitcompletIN.txt conţine pe prima linie numărul n. Urmează un număr k, apoi k numere naturale distincte cuprinse între 1 și n, reprezentând vârfurile din A. Mulțimea B conține toate numerele naturale cuprinse între 1 și n care nu sunt în A.

Date de ieşire

Fişierul de ieşire bipartitcompletOUT.txt va conţine matricea de adiacență a grafului construit, câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricţii şi precizări

• 1 < k < n ≤ 100

Exemplul 1:

bipartitcompletIN.txt

7
3 
4 6 3

bipartitcompletOUT.txt

0 0 1 1 0 1 0 
0 0 1 1 0 1 0 
1 1 0 0 1 0 1 
1 1 0 0 1 0 1 
0 0 1 1 0 1 0 
1 1 0 0 1 0 1 
0 0 1 1 0 1 0 

Exemplul 2 :

bipartitcompletIN.txt

1001
3 
4 6 3

bipartitcompletOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(k, n):

   if not (1 < k < n <= 100):
       with open("bipartitcompletOUT.txt", 'w') as f:
           f.write("Datele nu corespund restrictiilor impuse")
       return False
   return True

def construieste_graf(n, A):

   # Inițializăm matricea de adiacență cu zerouri
   graf = [[0] * n for _ in range(n)]

   # Marcam conexiunile dintre vârfurile din A și B
   for i in A:
       for j in range(1, n + 1):
           if j not in A:
               graf[i - 1][j - 1] = 1
               graf[j - 1][i - 1] = 1  # Adăugăm și conexiunea inversă

   return graf

def scrie_matrice_in_fisier(matrice, nume_fisier):

   with open(nume_fisier, 'w') as f:
       for linie in matrice:
           f.write(' '.join(map(str, linie)) + '\n')

if __name__ == "__main__":

   # Citim datele de intrare din fișier
   with open("bipartitcompletIN.txt", 'r') as f:
       n = int(f.readline().strip())
       k = int(f.readline().strip())
       A = list(map(int, f.readline().strip().split()))

   # Verificăm restricțiile
   if not verifica_restrictii(k, n):
       exit()

   # Construim graful bipartit
   graf = construieste_graf(n, A)

   # Scriem matricea de adiacență în fișierul de ieșire
   scrie_matrice_in_fisier(graf, "bipartitcompletOUT.txt")

</syntaxhighlight>