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
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")