Описание
Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существует пути как из четного, так и из нечетного числа ребер

Задание
Напишите программу, которая:

  1. Определяет, является ли заданный граф четно-нечетным

  2. В случае отрицательного ответа на пункт А находит максимальное подмножество Х вершин графа такое, что для любых двух вершин i и j из Х выполняется следующее условие: все пути между i и j состоят из четного числа ребер


Входные данные
Первая строка входного файла содержит число вершин графа N (1≤N≤100), a каждая последующая - пару чисел (i,j), означающих, что в графе присутствует ребро, соединяющее вершины с номерами i и j

Выходные данные
Первая строка выходного файла должна содержать ответ на пункт (1) в форме "YES"/"NO". В случае отрицательного ответа на пункт (1) вторая строка должна содержать количество вершин в множестве X, а третья - номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них


Например:

EVENGR
3
1 2

EVENGR
NO
2
2 3
Идеи
Поиск в глубину

Комментарии
Выполняем обход графа в глубину (см., например, [Липский 88, п.2.2]), одновременно раскрашивая вершины в белый и черный цвета в «шахматном порядке». А именно, пусть мы пришли в очередную вершину из вершины, имеющей, для определенности, черный цвет. Тогда красим ее в белый цвет и перебираем по очереди все соседние вершины. Если какая-то из них окрашена в черный цвет, то пропускаем ее, если в белый - выводим сообщение о том, что граф четно-нечетный и выходим из программы. Если же попадется неокрашенная вершина, то переходим в нее, выполняя тем самым шаг обхода в глубину

Окрасив все компоненты связности, для каждой из них выберем наибольшее по мощности из множеств ее черных и белых вершин. Объединив все выбранные множества, получим, очевидно, ответ на пункт (2) задачи

Фактически, граф, не являющийся четно-нечетными, - это просто двудольный граф, а наша раскраска помогает выделить его доли. Если для каждой компоненты связности выделить левую и правую долю можно двумя способами, то для всего графа вариантов сделать это 2k, где k - число компонент связности

 


Решение

{$A+,B-,D+,E+,F-,G+,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 16384,0,655360}

Program evengraph;
Uses Dos;
Var A,B,C,D,E,F,N,M : LongInt;
G : Array[1..100,1..100] of Boolean;
Y : Array[1..100,1..100] of Byte;
X,S : Array[1..100] of Byte;
Bol : Boolean;
 
Procedure ReadFile;
Begin
  Assign(Input,'evengraph.in');
  ReSet(Input);
  ReadLn(N);
  FillChar(G,SizeOf(G),False);
  M:=0;
  While Not SeekEof do
  Begin
    Inc(M);
    ReadLn(A,B);
    G[A,B]:=True;
    G[B,A]:=True;
  End;
  Close(Input);
End;
 
Procedure Rec(Q,W : Byte);
Var A : Byte;
Begin
  If X[W]<>0 then Exit;
  X[W]:=Q;
  For A:=1 to N do
    If Y[W,A]=2 then
    Begin
      Rec(Q,A);
    End;
End;
 
Procedure Work;
Var
O,U,Z : Array[1..300] of Byte;
K,I,J : LongInt;
Begin
  FillChar(Y,SizeOf(Y),0);
  For K:=1 to N do
  Begin
    Y[K,K]:=2;
    FillChar(Z,SizeOf(X),0);
    Z[K]:=1;
    Repeat
      Bol:=True;
      For A:=1 to N do
        If Z[A]=1 then
        Begin
          Bol:=False;
          For B:=1 to N do
            If G[A,B] then
            Begin
              If Y[K,A]=3 then C:=3 else C:=3-Y[K,A];
              If Y[K,B]<>C then Begin Z[B]:=3;Y[K,B]:=Y[K,B] or C;End;
            End;
          Z[A]:=2;
        End;
      For A:=1 to N do
        If Z[A]=3 then Z[A]:=1;
    Until Bol;
  End;
 
  Bol:=False;
  For A:=1 to N do
    For B:=1 to N do
      If Y[A,B]=3 then
      Begin
        Bol:=True;
        Break;
      End;
  If Bol then
  Begin
    WriteLn('YES');
    Exit;
  End;
  WriteLn('NO');
  FillChar(X,SizeOf(X),0);
  FillChar(S,SizeOf(S),0);
  B:=0;
  For A:=1 to N do
    If X[A]=0 then
    Begin
      Inc(B);
      Rec(B,A);
    End;
  FillChar(Z,SizeOf(Z),0);
  For A:=1 to N do
    Inc(Z[X[A]]);
  A:=1;
  While Z[A]<>0 do
  Begin
    FillChar(O,SizeOf(O),1);
    For B:=1 to N do
      If X[B]=A then
      Begin
        O[B]:=0;
        For C:=1 to N do
          If (X[C]<>A) and ((Y[B,C]<>0) or (Y[B,C]=1)) then O[C]:=0;
      End;
    For B:=1 to N do
      For C:=1 to N do
        If (O[B]=1) and (O[C]=1) and (B<>C) and (Y[B,C]=1) then Begin O[B]:=0; Break; End;
    FillChar(U,SizeOf(U),0);
    For B:=1 to N do
      If O[B]=1 then U[X[B]]:=1;
    For B:=1 to N do
      If U[X[B]]=1 then O[B]:=1;
    C:=0;
    For B:=1 to N do
      If O[B]=1 then Inc(C);
    Inc(Z[A],C);
    Inc(A);
  End;
 
  B:=-1;
  For A:=1 to N do
    If Z[A]>B then
    Begin
      B:=Z[A];
      C:=A;
    End;
  WriteLn(B);
  A:=C;
  FillChar(O,SizeOf(O),1);
  For B:=1 to N do
    If X[B]=A then
    Begin
      O[B]:=0;
      For C:=1 to N do
        If (X[C]<>A) and ((Y[B,C]<>0) or (Y[B,C]=1)) then O[C]:=0;
    End;
  For B:=1 to N do
    For C:=1 to N do
      If (O[B]=1) and (O[C]=1) and (B<>C) and (Y[B,C]=1) then Begin O[B]:=0; Break; End;
  FillChar(U,SizeOf(U),0);
  For B:=1 to N do
    If O[B]=1 then U[X[B]]:=1;
  For B:=1 to N do
    If U[X[B]]=1 then O[B]:=1;
  For B:=1 to N do
    If O[B]=1 then X[B]:=A;
  C:=A;
  For A:=1 to N do
  If X[A]=C then
  Begin
    Write(A,' ');
  End;
End;
 
Begin
  ReadFile;
  Assign(Output,'evengraph.out');
  ReWrite(Output);
  Work;
  Close(Output);
End.

 

© Особенности национальных задач по информатике