Page 331, Exercise 1

BiPartitioning a graph is often called the "two-color" problem.  That is, can we color the vertices of the graph using two colors, say red and blue, so that no edge on the graph connects vertices of the same color.  The solution is to create an array whose indices range from 1 to the maximum number of vertices in the array.  The component type  of the array holds the color code, which ranges from 0 (color red), to 1 (color blue), to 2
(not yet colored).  The algorithm arbitrarily picks a starting vertex and marks it with a 1.  All vertices adjacent to it are marked with a 0 and placed on a stack.  The algorithm removes a vertex from the stack and processes all of its vertices.  If these vertices are unmarked, they are marked with the opposite color of their parent.  Previously marked vertices must have the opposite color of the current vertex, or the graph cannot be bipartitioned. 
If the algorithm halts with an empty stack, the graph has been bipartitioned.  The array match can be used to print out the two sets.  If it halts with done set to true, the graph cannot be bipartitioned. The time complexity of this algorithm is O(n+e), where n = number of vertices and e = number of edges. 

BiPartitioning Algorithm 
Algorithm BiPartite(Adj:AdjList; N:integer
          var Match:MatchType; var done:boolean)
/*(determine if the graph can be partitioned into two disjoint sets*/
var i, Top:integer;
    Stack:array[0..MaxSize] of integer;
    p:listPointer;
begin
  for i←0 to n-1 do
  /*all elements of match are unmarked*/
    match[0] ←2;
  Top ← 0;
  /*mark the first vertex as a one*/
  p←Adj[0];
  match[0]←1;
  while (p != NULL) do begin
  /*mark all of the vertices adjacent to one with a zero
   place these vertices on the stack*/
    top ←top +1;
    stack[top] ← p.vertex;
    match[p.vertex] ← 0;
    p ←p.link
  end;
  i←1;
  done←false;
  while (Top > 0) and not done do begin
  /*remove a vertex from the stack examine each vertex adjacent to it  
   if unmarked, mark with the opposite mark of the vertex
   if marked, check to see that the signs are opposite
   if the signs are the same, the graph cannot be bipartitioned */
    i←stack[top];
    top← top-1;
    p←adj[i];
    while (p != nil) and !done do begin
    /*examine each vertex adjacent to i*/
      if match[p.vertex] > 1 then begin
        if (match[i] = 0) then
           match[p.vertex]←1
        else
           match[p.vertex] ←0;
        top← top+1;
        stack[top] ← p.vertex
      end
      else if (match[i] = match[p.vertex]) then
          done ← true;
      p ←p.link
    end;
  end;
end;