5705. Двудольный граф

Medium 0 решили
Неориентированный граф. Верните true, если вершины можно раскрасить в два цвета так, что каждое ребро соединяет разные цвета (граф двудольный).
Это равносильно отсутствию нечётного цикла. Граф без рёбер и несвязный граф из чётных циклов — двудольны. Нечётный цикл в любой компоненте → false.

Примеры:

Вход: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Выход: true
Объяснение: Чётный цикл.
Вход: n = 3, edges = [[0,1],[1,2],[2,0]]
Выход: false
Объяснение: Нечётный цикл.
Вход: n = 1, edges = []
Выход: true
Объяснение: Без рёбер двудолен.

Ограничения:

1 <= n <= 2000

Теги:

Графы

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

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