Статья Автор: Дубинин Дмитрий

"Проверка на двудольность"

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def is_bipartite(n, graph):
    color = [-1] * (n + 1)
    
    for start in range(1, n + 1):
        if color[start] == -1:
            queue = [start]
            color[start] = 0
            idx = 0
            
            while idx < len(queue):
                v = queue[idx]
                idx += 1
                for to in graph[v]:
                    if color[to] == -1:
                        color[to] = 1 - color[v]
                        queue.append(to)
                    elif color[to] == color[v]:
                        return False
    return True

print(is_bipartite(n, graph))

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать