0471 - Bipartit

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n, precum si o mulțime A de vârfuri ale grafului. Considerăm mulțimea B formată din vărfurile grafului care nu aparțin lui A. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile A și B.

Date de intrare

Fişierul de intrare bipartitIN.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. Urmează un număr k, apoi k numere naturale distincte cuprinse între 1 și n, reprezentând vârfurile din A.

Date de ieşire

Fişierul de ieşire bipartitOUT.txt va conţine pe prima linie mesajul DA, dacă graful este bipartit peste partiția formată din mulțimile A și B, respectiv NU în caz contrar.

Restricţii şi precizări

• 1 < k < n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplul 1

bipartitIN.txt:

7 6

1 4

1 6

6 5

3 2

3 5

3 7

3

4 6 3

bipartitOUT.txt:

DA

Exemplul 2

bipartitIN.txt:

999 6

1 4

1 6

6 5

3 2

3 5

3 7

3

4 6 3

Output:

Datele de intrare nu respectă restricțiile.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def is_bipartite(graph, vertices_in_a):

   colors = {}
   queue = []

   for vertex in vertices_in_a:
       colors[vertex] = 1
       queue.append(vertex)

   while queue:
       current_vertex = queue.pop(0)

       for neighbor in graph[current_vertex]:
           if neighbor not in colors:
               colors[neighbor] = -colors[current_vertex]
               queue.append(neighbor)
           elif colors[neighbor] == colors[current_vertex]:
               return False

   return True

def is_valid_input(n, m, k, edges):

   if not (1 < k < n <= 100):
       return False

   for i, j in edges:
       if not (1 <= i <= n and 1 <= j <= n):
           return False

   return True

1. Citirea datelor de intrare din fișier

with open("bipartitIN.txt", "r") as input_file:

   n, m = map(int, input_file.readline().split())
   edges = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

   k = int(input_file.readline())
   vertices_in_a = set(map(int, input_file.readline().split()))

1. Verificare restricții pentru datele de intrare

if not is_valid_input(n, m, k, edges):

   print("Datele de intrare nu respectă restricțiile.")

else:

   # Inițializare graful
   graph = {i: [] for i in range(1, n + 1)}

   # Adăugare muchii în graf
   for i, j in edges:
       graph[i].append(j)
       graph[j].append(i)

   # Verificare dacă graful este bipartit
   result = is_bipartite(graph, vertices_in_a)

   # Scrierea rezultatului în fișierul de ieșire
   with open("bipartitOUT.txt", "w") as output_file:
       output_file.write("DA" if result else "NU")

</syntaxhighlight>