0472 - Bipartit 1

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Să se verifice dacă graful este bipartit.

Date de intrare

Fişierul de intrare bipartit1in.txt conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele m 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 bipartit1out.txt va conţine pe prima linie mesajul DA, dacă graful este bipartit, respectiv NU în caz contrar.

Dacă mesajul este DA, următoarele două linii vor conţine două mulţimi care formează partiţia vârfurilor. Elementele fiecărei mulţimi vor fi afişate în ordine crescătoare, separate prin exact un spaţiu. Prima mulţime va fi cea care conţine vârful 1

Restricții și precizări

• 1 < n ⩽ 15
• 1 ⩽ i , j ⩽ n

Exemplul 1

bipartit1in.txt

7 6
1 4
1 6
6 5
3 2
3 5
3 7

bipartit1out.txt

Datele de intrare corespund restrictiilor impuse.
DA
1 2 5 7 
3 4 6 

Exemplul 2

bipartit1in.txt

ijtijgijrigmfg

bipartit1out.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
def validare(n_validare, muchii_validare):
    # Verificăm dacă n este în intervalul 1-15
    if n_validare < 1 or n_validare > 15:
        raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-15
    for muchie in muchii_validare:  # Parcurgem lista de muchii
        # Verificăm dacă valoarea absolută a fiecărui vârf este în intervalul 1-n
        if abs(muchie[0]) < 1 or abs(muchie[0]) > n_validare or abs(muchie[1]) < 1 or abs(muchie[1]) > n_validare:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse.\n")


# Funcția este_bipartit verifică dacă graful este bipartit
def este_bipartit(n_bipartit, muchii_bipartit):
    # Inițializăm culorile vârfurilor cu -1
    culoare_bipartit = [-1] * (n_bipartit + 1)
    # Construim lista de adiacență a grafului
    lista_adiacenta = [[] for _ in range(n_bipartit + 1)]
    for muchie in muchii_bipartit:
        lista_adiacenta[muchie[0]].append(muchie[1])
        lista_adiacenta[muchie[1]].append(muchie[0])
    # Parcurgem vârfurile grafului
    for i in range(1, n_bipartit + 1):
        # Dacă vârful nu a fost colorat și nu poate fi colorat, atunci graful nu este bipartit
        if culoare_bipartit[i] == -1 and not colorare(i, 1, culoare_bipartit, lista_adiacenta):
            return False, culoare_bipartit
    return True, culoare_bipartit


# Funcția colorare încearcă să coloreze vârfurile grafului astfel încât să fie bipartit
def colorare(v, c, culoare_color, lista_adiacenta):
    # Colorăm vârful v cu culoarea c
    culoare_color[v] = c
    # Parcurgem vecinii vârfului v
    for u in lista_adiacenta[v]:
        # Dacă vecinul u are aceeași culoare cu v, atunci graful nu poate fi bipartit
        if culoare_color[u] == c:
            return False
        # Dacă vecinul u nu a fost colorat și nu poate fi colorat, atunci graful nu poate fi bipartit
        if culoare_color[u] == -1 and not colorare(u, 1 - c, culoare_color, lista_adiacenta):
            return False
    return True


if __name__ == '__main__':
    file_in = open("bipartit1in.txt", "r")
    file_out = open("bipartit1out.txt", "w")

    try:
        # Citim numărul de vârfuri și de muchii
        n_main, m_main = map(int, file_in.readline().split())
        # Citim muchiile
        muchii_main = [list(map(int, linie.split())) for linie in file_in.readlines()]
        # Validăm datele de intrare
        validare(n_main, muchii_main)
        # Verificăm dacă graful este bipartit
        bipartit, culoare = este_bipartit(n_main, muchii_main)
        if bipartit:
            file_out.write("DA\n")
            # Construim listele de vârfuri pentru cele două mulțimi
            lista1 = [i for i in range(1, n_main + 1) if culoare[i] == 1]
            lista2 = [i for i in range(1, n_main + 1) if culoare[i] == 0]
            file_out.write(' '.join(map(str, lista1)) + '\n')
            file_out.write(' '.join(map(str, lista2)) + '\n')
        else:
            file_out.write("NU\n")

    # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
    # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse.")