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