Czy jest dwudzielny?
Lekcja 14 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.
Graf jest dwudzielny, jeśli można podzielić jego wierzchołki na dwie grupy tak, aby każda krawędź łączyła wierzchołek z jednej grupy z wierzchołkiem z drugiej. Pomyśl o kolorach czerwonym i niebieskim: każda krawędź ma jeden czerwony i jeden niebieski koniec.
BFS zapewnia prosty test. Zacznij od dowolnego wierzchołka, pokoloruj go na czerwono i przechodź dalej. Każdy nowy sąsiad otrzymuje kolor przeciwny do koloru wierzchołka, z którego dotarliśmy. Jeśli kiedykolwiek trafimy na krawędź łączącą dwa wierzchołki o tym samym kolorze, graf nie jest dwudzielny. Klasycznym przykładem jest cykl o nieparzystej długości: trójkąt 0-1-2-0 wymusza, by wierzchołek 0 był jednocześnie czerwony i niebieski.
Warto pamiętać o jednej rzeczy: jeśli graf ma kilka składowych spójnych, trzeba rozpocząć nowe kolorowanie dwoma kolorami w każdej z nich. Najprostszy sposób to pojedyncza pętla przechodząca po wszystkich wierzchołkach i rozpoczynająca BFS za każdym razem, gdy napotka niepokolorowany wierzchołek.
Wyzwanie
ŁatwyNapisz funkcję isBipartite, która przyjmuje dwuwymiarową tablicę liczb całkowitych adjacency oraz tablicę liczb całkowitych vertices i zwraca true, jeśli graf jest dwudzielny, a w przeciwnym razie false.
Zbuduj graf (dodaj każdy wierzchołek za pomocą addVertex, a następnie każdą krawędź za pomocą addEdge). Następnie pokoloruj go dwoma kolorami, wykonując BFS dla każdej składowej spójnej: przypisz kolor 0 wierzchołkowi początkowemu, a każdemu sąsiadowi przypisz kolor 1 - color[u]. Jeśli znajdziesz krawędź, której oba końce mają już ten sam kolor, zwróć false. W przeciwnym razie zwróć true.
Musisz użyć klasy Graph (udostępnionej w graph) — nie używaj wbudowanych elementów języka (map, zbiorów) do reprezentowania sąsiedztwa. Pomocnicze struktury danych algorytmu (mapa kolorów, kolejka) mogą korzystać z typów biblioteki standardowej.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Grafy – struktury danych, seria nr 9
Poćwicz samodzielnie: Kompilator C online