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

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