Проверка на двудольность графа
Граф считается двудольным, если его можно раскрасить в два цвета так, чтобы никакие две соседние вершины не были окрашены одинаково.
Определение двудольности графа помогает выявлять важные структуры и свойства, что упрощает решение задач в таких сферах, как планирование, распределение ресурсов и разрешение конфликтов. Кроме того, двудольные графы позволяют использовать более простые алгоритмы и применять оптимизации при поиске максимального паросочетания и раскраске графа.
Вам задан неориентированный граф с числом вершин
v и числом рёбер e. Необходимо проверить, является ли данный граф двудольным.Входные данные
В первой строке входных данных содержатся два целых числа
v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).В следующих
e строках записаны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), где указывается, что вершина v1 соединена с вершиной v2, и наоборот.Выходные данные
Программа должна вывести
Yes, если заданный граф двудольный, и No — в противном случае.Примеры
Ввод | Вывод |
2 1
2 1 | Yes |
3 2
2 1
1 3 | Yes |
3 3
1 2
1 3
2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB