// Testowanie dwudzielności grafu
// Data: 24.11.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program test_bigraph;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push ( v : integer );
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push ( v : integer );
var
  p : PslistEl;
begin
  new ( p );
  p^.next := nil;
  p^.v := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose ( p );
  end;
end;

// Funkcja testuje dwudzielność grafu
// n - liczba wierzchołków grafu
// A - tablica list sąsiedztwa
//-----------------------------------
function isBipartite ( n : integer; var A : TList ) : boolean;
var
  Q     : queue;
  C     : array of integer;
  v, u, i : integer;
  p     : PslistEl;

begin
  SetLength ( C, n );      // Tworzymy tablicę kolorów
  for i := 0 to n - 1 do C [ i ] := 0;

  Q.init;                  // Tworzymy pustą kolejkę

  for i := 0 to n - 1 do   // Przechodzimy przez kolejne wierzchołki
    if C [ i ] = 0 then    // Szukamy wierzchołka szarego
    begin
      C [ i ] := 1;        // Wierzchołek startowy kolorujemy na czerwono
      Q.push ( i );        // i umieszczamy w kolejce

      while Q.empty = false do // Przejście BFS
      begin
        v := Q.front;      // Pobieramy wierzchołek z kolejki
        Q.pop;             // Pobrany wierzchołek usuwamy z kolejki
        p := A [ v ];      // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          u := p^.v;       // pobieramy z listy sąsiedztwa numer sąsiada
          if C [ u ] = C [ v ] then
          begin
            SetLength ( C, 0 );
            Q.destroy;
            Exit ( false );      // Sąsiad ma ten sam kolor
          end;

          if C [ u ] = 0 then    // Jeśli wierzchołek nie jest odwiedzony, 
          begin
            C [ u ] := -C [ v ]; // kolorujemy go na kolor przeciwny
            Q.push ( u );        // i umieszczamy w kolejce
          end;
          p := p^.next;  // Następny sąsiad
        end;
      end;
    end;

  SetLength ( C, 0 );

  isBipartite := true;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n, m, i, v1, v2 : integer;
  p, r         : PslistEl;
  A           : TList;

begin
  read ( n, m );         // Czytamy liczbę wierzchołków i krawędzi

  SetLength ( A, n );    // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A [ i ] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read ( v1, v2 );     // Wierzchołek startowy i końcowy krawędzi
    new ( p );           // Tworzymy nowy element
    p^.v := v2;          // Numerujemy go jako v2
    p^.next := A [ v1 ]; // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] := p;
    new ( p );           // Krawędź w drugą stronę, bo graf jest nieskierowany
    p^.v := v1;
    p^.next := A [ v2 ];
    A [ v2 ] := p;
  end;

  if isBipartite ( n, A ) then writeln ( 'BIPARTITE GRAPH' ) else writeln ( 'NOT A BIPARTITE GRAPH' );

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A [ i ];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose ( r );
    end;
  end;

  SetLength ( A, 0 );
end.

// Testowanie dwudzielności grafu
// Data: 24.11.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = -2147483647;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

struct slistEl
{
  slistEl * next;
  int v;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue( );      // konstruktor
    ~queue( );     // destruktor
    bool empty ( void );
    int  front ( void );
    void push ( int v );
    void pop ( void );
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue( )
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue( )
{
  while( head ) pop( );
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty ( void )
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front ( void )
{
  if( head ) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push ( int v )
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if( tail ) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop ( void )
{
  if( head )
  {
    slistEl * p = head;
    head = head->next;
    if( !head ) tail = NULL;
    delete p;
  }
}

// Funkcja testuje dwudzielność grafu
// n - liczba wierzchołków grafu
// A - tablica list sąsiedztwa
//-----------------------------------
bool isBipartite ( int n, slistEl ** A )
{
  queue Q;
  int * C;
  int v, u, i;
  slistEl * p;

  C = new int [ n ];      // Tworzymy tablicę kolorów
  for( i = 0; i < n; i++ ) C [ i ] = 0;

  for( i = 0; i < n; i++ )  // Przechodzimy przez kolejne wierzchołki
    if( !C [ i ] )        // Szukamy wierzchołka szarego
    {
      C [ i ] = 1;        // Wierzchołek startowy kolorujemy na czerwono
      Q.push ( i );       // i umieszczamy w kolejce

      while( !Q.empty( ) ) // Przejście BFS
      {
        v = Q.front( );   // Pobieramy wierzchołek z kolejki
        Q.pop( );         // Pobrany wierzchołek usuwamy z kolejki
        for( p = A [ v ]; p; p = p->next ) // Przeglądamy sąsiadów wierzchołka v
        {
          u = p->v;       // pobieramy z listy sąsiedztwa numer sąsiada
          if( C [ u ] == C [ v ] )
          {
            delete [ ] C;
            return false; // Sąsiad ma ten sam kolor
          }

          if( !C [ u ] )  // Jeśli wierzchołek nie jest odwiedzony, 
          {
            C [ u ] = -C [ v ];  // kolorujemy go na kolor przeciwny
            Q.push ( u ); // i umieszczamy w kolejce
          }
        }
      }
    }

  delete [ ] C;

  return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main( )
{
  int n, m, i, v1, v2;
  slistEl * p, * r, ** A;

  cin >> n >> m;           // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [ n ]; // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for( i = 0; i < n; i++ ) A [ i ] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A [ v1 ]; // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] = p;
    p = new slistEl;    // Krawędź w drugą stronę, bo graf jest nieskierowany
    p->v = v1;
    p->next = A [ v2 ];
    A [ v2 ] = p;
  }

  if( isBipartite ( n, A ) ) cout << "BIPARTITE GRAPH"; else cout << "NOT A BIPARTITE GRAPH";

  cout << endl;

  // Usuwamy tablicę list sąsiedztwa

  for( i = 0; i < n; i++ )
  {
    p = A [ i ];
    while( p )
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [ ] A;

  return 0;
}

' Testowanie dwudzielności grafu
' Data: 24.11.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor( )
    Declare Destructor( )
    Declare Function empty( ) As Integer
    Declare Function front As Integer
    Declare Sub push ( ByVal v As Integer )
    Declare Sub pop( )
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue( )
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue( )
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty( ) As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front( ) As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push ( ByVal v As Integer )
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop( )
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Funkcja testuje dwudzielność grafu
' n - liczba wierzchołków grafu
' A - tablica list sąsiedztwa
'-----------------------------------
Function isBipartite ( ByVal n As integer, ByVal A As slistEl Ptr Ptr ) As Integer

  Dim As queue Q
  Dim As Integer Ptr C
  Dim As Integer v, u, i
  Dim As slistEl Ptr p

  C = New Integer [ n ]     ' Tworzymy tablicę kolorów
  For i = 0 To n - 1
  	 C [ i ] = 0
  Next

  For i = 0 To n - 1        ' Przechodzimy przez kolejne wierzchołki
    If C [ i ] = 0 Then     ' Szukamy wierzchołka szarego
      C [ i ] = 1           ' Wierzchołek startowy kolorujemy na czerwono
      Q.push ( i )          ' i umieszczamy w kolejce

      While Q.empty( ) = 0  ' Przejście BFS
        v = Q.front( )      ' Pobieramy wierzchołek z kolejki
        Q.pop( )            ' Pobrany wierzchołek usuwamy z kolejki
        p = A [ v ] 
        While p             ' Przeglądamy sąsiadów wierzchołka v
          u = p->v          ' pobieramy z listy sąsiedztwa numer sąsiada
          If C [ u ] = C [ v ] Then
            Delete [ ] C
            Return 0        ' Sąsiad ma ten sam kolor
          End If

          If C [ u ] = 0 Then  ' Jeśli wierzchołek nie jest odwiedzony, 
            C [ u ] = -C [ v ] ' kolorujemy go na kolor przeciwny
            Q.push ( u )       ' i umieszczamy w kolejce
          End If
          
          p = p->Next       ' Następny wierzchołek
          
        Wend
      Wend
    End If
  Next
  
  Delete [ ] C

  Return 1
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As slistEl Ptr p, r
Dim As slistEl Ptr Ptr A

Open Cons For Input As #1

Input #1, n, m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [ n ] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A [ i ] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1, v1, v2     ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A [ v1 ]   ' Dodajemy go na początek listy A [ v1 ] 
  A [ v1 ] = p
  p = new slistEl      ' Krawędź w drugą stronę, bo graf jest nieskierowany
  p->v = v1
  p->next = A [ v2 ] 
  A [ v2 ] = p
Next

Close #1

If isBipartite ( n, A ) Then
  Print "BIPARTITE GRAPH"
Else
  Print "NOT A BIPARTITE GRAPH"
EndIf

' Usuwamy tablicę list sąsiedztwa

For i = 0 To n - 1
  p = A [ i ] 
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [ ] A

End