View source for 0473 - Bipartit Complet

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

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

= Date de ieşire =
Fişierul de ieşire <code>bipartitcompletOUT.txt</code> 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 =

* <code>1 < k  < n ≤ 100</code>

= Exemplul 1: =
<code>bipartitcompletIN.txt</code>
 7
 3 
 4 6 3
<code>bipartitcompletOUT.txt</code>
 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 : =
<code>bipartitcompletIN.txt</code>
 1001
 3 
 4 6 3
<code>bipartitcompletOUT.txt</code>
 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>