(*                                      Vertex Coloring Problem
                                        Ordering Algorithms

        INPUT           :  The associated datafile is "OrderingDatafile"
                           1st number represents # of vertices of a graph to
                                 be colored
                           2nd set of numbers represents the graph; fields
                                DEGREE and ADJLIST.

        OUTOUT          :  Output is
                           SEQ[1..N], array which contains a corresponding
                           ordering of vertices of the graph, either
                           largest-first ordering or a smallest-last ordering.

        Algorithm       :  The algorithm finds either a latgest-first
                           (if BOOL =  FALSE) or a smallest-last ordering
                           (if BOOL = TRUE) of vertices of a graph. A radix
                           sort algorithm is used to find the former ordeing.
                           Since the vertex  degrees are from the range 0 and
                           N-1, where N is the number of vertices in a graph,
                           a radix sort algorithm  can be implemented to
                           run in time O(N). When BOOL =TRUE, a smallest-last
                           ordering is generated in the second part of the
                           algorithm.  The time complexity is O(M).
                                                                *)


program Ordering_Algorithm (input,output,OrderingDatafile,OrderingOutfile);

const	maxvar = 50;


type	CHARFILE = file of char;
	ARRN = array [1..maxvar] of integer;
	ARR0N = array [0..maxvar] of integer;
        VERTPOINT = ^VERTLIST;
        GRAPH = array [1..maxvar] of
		record
		  DEGREE : integer;
		  COLOR : integer;
		  ADJLIST : VERTPOINT
		end;
	VERTLIST = record
		    VERTEX : integer;
		    NEXT : VERTPOINT
		   end;

var	N : integer;
	BOOL : boolean;
	GR : GRAPH;
	SEQ : ARRN;
	Nextint : integer;
        OrderingDatafile : CHARFILE;
        OrderingOutfile  : CHARFILE;
	temp : integer;
        
procedure Infile (var N  : integer;
		  var GR : GRAPH;
		  var Nextint : integer);

var count : integer;
    Newelement : VERTPOINT;
begin
  reset(OrderingDatafile);
  readln (OrderingDatafile,Nextint);
  N := Nextint;
  for count := 1 to N do
  begin
    GR[count].ADJLIST := nil;
    read (OrderingDatafile,Nextint);
    GR[count].DEGREE := Nextint;
    while (not eoln(OrderingDatafile)) do
    begin
      new (Newelement);
      read(OrderingDatafile,Nextint);
      Newelement^.VERTEX := Nextint;
      Newelement^.NEXT := GR[count].ADJLIST;
      GR[count].ADJLIST := Newelement;
    end;
    readln(OrderingDatafile);
  end;
end;


   

function ORDERING(
       N   :integer;
       BOOL:boolean;
   var GR  :GRAPH;
   var SEQ :ARRN):integer;

   { FUNCTION ORDERING ORDERS VERTICES OF THE GRAPH. IF BOOL=TRUE
     THEN SEQ[1], SEQ[2], ..., SEQ[N] IS A SMALLEST LAST ORDERING
     AND IF BOOL=FALSE THEN IT IS A LARGEST-FIRST ORDERING. }

   var BOUND,I,I1,I2,J1,J2,J3,J4,J5:integer;
       INN,D                       :ARRN;
       RAD,RADIX                   :ARR0N;
       P                           :VERTPOINT;
begin
   for I:=0 to N do RADIX[I]:=0;
   for I:=1 to N do begin
      I1:=GR[I].DEGREE;  RADIX[I1]:=RADIX[I1]+1
   end;
   I1:=0;  I:=N;
   while I1 < N do begin
      I:=I-1;  I1:=RADIX[I]+I1;
      RADIX[I]:=I1;  RAD[I]:=I1
   end;
   for I:=1 to N do begin
      I1:=GR[I].DEGREE;  I2:=RADIX[I1];
      INN[I]:=I2;
      SEQ[I2]:=I;  RADIX[I1]:=I2-1
   end;  { for I }
      { SEQ[1], SEQ[2], ..., SEQ[N] IS THE SEQUENCE OF
        VERTICES ORDERED BY NON-INCREASING DEGREE }
   BOUND:=1;
   if BOOL then begin               { FINDING A SMALLEST-LAST ORDER }
      for I:=1 to N do D[I]:=GR[I].DEGREE;
      for I:=N downto 3 do begin
         I1:=SEQ[I];  J1:=D[I1];
         if J1 > BOUND then BOUND:=J1;
         RAD[J1]:=I-1;
         P:=GR[I1].ADJLIST;
         while P <> nil do begin
            J1:=P^.VERTEX;  J2:=INN[J1];
            if J2 < I then begin
               J3:=D[J1];  J4:=RAD[J3];  J5:=SEQ[J4];
               SEQ[J2]:=J5;  SEQ[J4]:=J1;
               INN[J5]:=J2;  INN[J1]:=J4;
               RAD[J3]:=J4-1;
               D[J1]:=J3-1
            end;  { if J2 < I }
            P:=P^.NEXT
         end  { while P <> nil }
      end;  { for I }
      BOUND:=BOUND+1;
   end  { if BOOL }
   else
      for I:=2 to N do begin
         J1:=GR[SEQ[I]].DEGREE+1;
         if J1 > I then J1:=I;
         if J1 > BOUND then BOUND:=J1
      end;  { for I, else: NOT BOOL }
   ORDERING:=BOUND;
end;  { ORDERING }




procedure Outfile (SEQ : ARRN);

var count : integer;

begin
  rewrite(OrderingOutfile);
  writeln (OrderingOutfile,' The solution obtained using Ordering Algorithm is as follows ');
  writeln (OrderingOutfile,'	BOOL	ORDERING');
  write (OrderingOutfile,'	',BOOL,'     ',temp:2);
  writeln(OrderingOutfile);
  writeln(OrderingOutfile);
  write (OrderingOutfile,' SEQ[1  ..',N:3,'] is ');
  for count := 1 to N do
  begin
    write (OrderingOutfile,'	  ',SEQ[count]:3);
  end;
  writeln(OrderingOutfile);
end;



begin (* main *)
  BOOL := false;
  Infile (N,GR,Nextint);
  temp := ORDERING (N,BOOL,GR,SEQ);
  Outfile(SEQ);
end.