Раскраска в два цвета

Пусть дан неориентированный граф G из N вершин. Требуется покрасить его в два цвета (черный и белый) так, что никакие две вершины одного цвета не будут смежными, либо сказать, что это невозможно.

Для решения этой задачи мы несколько видоизменим алгоритм обхода в глубину. Изменим смысл массива V: V[i]=0, если вершина i еще не была посещена, V[i]=1, если вершина i белого цвета, и V[i]=2, если вершина i черного цвета. Перед каждым рекурсивном вызовом процедуры DFS_Work(b) из процедуры DFS_Work(a) мы будем сравнивать значения V[a] и V[b]; должно выполняться условие V[a]+V[b]=3, иначе раскраска в два цвета невозможна.

Реализация алгоритма:

const
  MaxN = 100;

var
  N : Integer;
  G : array [1 .. MaxN,1 .. MaxN] of Boolean;
  V : array [1 .. MaxN] of Byte;

function DFS_Work_BiColor(A : Integer) : Boolean;
var
  B : Integer;
begin
  DFS_Work_BiColor := False;
  Writeln(A);
  for B := 1 to N do
    if G[A,B] then
    begin
      if V[b]=0 then
      begin
        V[b] := 3-V[A];
        if not DFS_Work_BiColor(B) then
          exit;
      end
      else
        if V[A]+V[b]<>3 then
          exit;
    end;
  DFS_Work_BiColor := True;
end;

function BiColor : Boolean;
var
  A : Integer;
begin
  BiColor := False;
  FillChar(V,sizeof(V),0);
  for A := 1 to N do
    if V[A]=0 then
    begin
      V[A] := 1;
      if not DFS_Work_BiColor(A) then
        exit;
    end;
  BiColor := True;
end;

Алгоритм раскраски графа в два цвета требует, как и алгоритм обхода в глубину, O(N^2) времени и O(N) памяти для графа, заданного матрицей смежности, и O(M+N) времени для графа, заданного списками смежности.