Editing 0471 - Bipartit

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

= Date de intrare =
Fişierul de intrare <code>bipartitIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>. Urmează un număr <code>k</code>, apoi <code>k</code> numere naturale distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând vârfurile din <code>A</code>.

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

= Restricţii şi precizări =

* <code>1 < k  < n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* 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

# 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()))

# 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>