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

<syntaxhighlight lang="python" line>

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

1. 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

1. 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>