Editing 0472 - Bipartit 1 (section)

== Rezolvare ==
<syntaxhighlight lang="python" line>
# 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.")


</syntaxhighlight>