Проверка на двудольность
Урок 14 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Граф является двудольным, если его вершины можно разделить на две группы так, чтобы каждое ребро соединяло вершину из одной группы с вершиной из другой. Представьте красный и синий цвета: у каждого ребра один конец красный, а другой — синий.
BFS (поиск в ширину) предоставляет простой способ проверки. Начните с любой вершины, раскрасьте её в красный цвет и двигайтесь наружу. Каждый новый сосед получает цвет, противоположный цвету вершины, из которой мы пришли. Если мы когда-нибудь увидим ребро, соединяющее две вершины одинакового цвета, граф не является двудольным. Классический пример нарушения — цикл нечётной длины: треугольник 0-1-2-0 заставляет вершину 0 быть одновременно и красной, и синей.
Важно помнить: если в графе несколько компонент связности, вам нужно начинать новую раскраску в два цвета для каждой из них. Самый простой шаблон — это один цикл по всем вершинам, который запускает BFS всякий раз, когда находит нераскрашенную вершину.
Задание
ЛегкоНапишите функцию isBipartite, которая принимает двумерный массив целых чисел adjacency и массив целых чисел vertices, и возвращает true, если граф является двудольным, и false в противном случае.
Постройте граф (используя addVertex для каждой вершины, затем addEdge для каждого ребра). Затем выполните 2-раскраску через BFS для каждой компоненты связности: назначьте начальный цвет 0, а каждому соседу присвойте цвет 1 - color[u]. Если вы обнаружите ребро, у которого оба конца уже имеют одинаковый цвет, верните false. В противном случае верните true.
Вы должны использовать класс Graph (предоставленный в graph) — не используйте встроенные средства языка (карты, множества) для моделирования смежности. Вспомогательные данные для алгоритма (карта цветов, очередь) могут использовать типы стандартной библиотеки.
Попробуйте сами
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}