AntalKrisztian: Pagină nouă: == 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 înt...

2023-12-29T18:44:18Z

Pagină nouă: == 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 înt...

New page

== 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 &les; 15'''
* '''1 &les; i , j &les; 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
<br>
== Exemplul 2 ==
; bipartit1in.txt
ijtijgijrigmfg
; bipartit1out.txt
Datele de intrare nu corespund restrictiilor impuse.
<br>
== 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>

0472 - Bipartit 1 - Revision history