#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define VERY_LARGE 1000000000

typedef struct _tnode {
   int degree;
   int vertex;
   struct _tnode *L, *R;
} tnode;

typedef tnode *tree;

typedef struct _hnode {
   int order;
   tree T;
   struct _hnode *next;
} hnode;

typedef hnode *heap;

typedef int **graph;

int *genrandseq ( int n )
{
   int i, j, *D, t;

   D = (int *)malloc(n * sizeof(int));
   t = 0;
   for (i=0; i<n; ++i) {
      D[i] = rand() % (n - 5);
      if (D[i] & 1) t ^= 1;
      if ((i == n-1) && (t == 1)) {
         if (D[i] == 0) ++D[i]; else --D[i];
      }
   }
   for (i=n-2; i>=0; --i) for (j=0; j<=i; ++j) if (D[j] < D[j+1]) {
      t = D[j]; D[j] = D[j+1]; D[j+1] = t;
   }
   printf("+++ Sequence generated:\n");
   for (i=0; i<n; ++i) printf("%4d%c%s", D[i], (i==n-1) ? '\n' : ',', ((i % 16 == 15) && (i != n-1)) ? "\n" : "");
   return D;
}

int isgraphic ( int *D, int n )
{
   int i, k, LHS, RHS;

   LHS = 0;
   for (k=0; k<n; ++k) {
      LHS += D[k];
      RHS = k * (k + 1);
      for (i=k+1; i<n; ++i) RHS += (D[i] < k+1) ? D[i] : k+1;
      if (LHS > RHS) return 0;
   }
   return 1;
}

tree tmerge ( tree T1, tree T2 )
{
   tree T;

   if ((T1 == NULL) || (T2 == NULL)) {
      fprintf(stderr, "*** Error: Invalid tree in tmerge...\n");
      exit(2);
   }
   if (T1 -> degree < T2 -> degree) {
      T = T1; T1 = T2; T2 = T;
   }
   T = T1 -> L;
   T1 -> L = T2;
   T2 -> R = T;
   T1 -> R = NULL;  /*** Not necessary ***/
   return T1;
}

void prnheap ( heap H )
{
   heap p;

   if (H) {
      p = H -> next;
      while (p != NULL) { printf("%d ", p -> order); p = p -> next; }
      printf("\n");
   }
}

heap hmerge ( heap H1, heap H2 )
{
   heap p1, p2, H, p, q;
   tree carry;
   int c;

   if ((H1 == NULL) || (H2 == NULL)) {
      fprintf(stderr, "*** Error: Invalid heap in hmerge...\n");
      exit(3);
   }
   p1 = H1 -> next; p2 = H2 -> next; carry = NULL; free(H1); free(H2);
   H = (heap)malloc(sizeof(hnode));        /* dummy node creation */
   p = H; carry = NULL; c = -1;
   while ((p1 != NULL) || (p2 != NULL)) {
      if (p1 == NULL) {
         if (carry == NULL) {                                        /* copy from p2 */
            p -> next = (heap)malloc(sizeof(hnode));
            p = p -> next;
            p -> order = p2 -> order;
            p -> T = p2 -> T;
            q = p2; p2 = p2 -> next; free(q);
         } else if (p2 -> order == c) {                             /* only create output carry */
            carry = tmerge(carry, p2 -> T);
            ++c;
            q = p2; p2 = p2 -> next; free(q);
         } else {                                                   /* use carry as current tree */
            p -> next = (heap)malloc(sizeof(hnode));
            p = p -> next;
            p -> order = c;
            p -> T = carry;
            carry = NULL;
         }
      } else if (p2 == NULL) {
         if (carry == NULL) {                                        /* copy from p1 */
            p -> next = (heap)malloc(sizeof(hnode));
            p = p -> next;
            p -> order = p1 -> order;
            p -> T = p1 -> T;
            q = p1; p1 = p1 -> next; free(q);
         } else if (p1 -> order == c) {                             /* only create output carry */
            carry = tmerge(carry, p1 -> T);
            ++c;
            q = p1; p1 = p1 -> next; free(q);
         } else {                                                   /* use carry as current tree */
            p -> next = (heap)malloc(sizeof(hnode));
            p = p -> next;
            p -> order = c;
            p -> T = carry;
            carry = NULL;
         }
      } else {
         if (carry == NULL) {
            if (p1 -> order < p2 -> order) {                        /* copy from p1 */
               p -> next = (heap)malloc(sizeof(hnode));
               p = p -> next;
               p -> order = p1 -> order;
               p -> T = p1 -> T;
               q = p1; p1 = p1 -> next; free(q);
            } else if (p1 -> order > p2 -> order) {                 /* copy from p2 */
               p -> next = (heap)malloc(sizeof(hnode));
               p = p -> next;
               p -> order = p2 -> order;
               p -> T = p2 -> T;
               q = p2; p2 = p2 -> next; free(q);
            } else {                                                /* only set output carry */
               carry = tmerge(p1 -> T, p2 -> T);
               c = p1 -> order + 1;
               q = p1; p1 = p1 -> next; free(q);
               q = p2; p2 = p2 -> next; free(q);
            }
         } else {
            if ((c < p1 -> order) && (c < p2 -> order)) {           /* set carry as current tree */
               p -> next = (heap)malloc(sizeof(hnode));
               p = p -> next;
               p -> order = c;
               p -> T = carry;
               carry = NULL;
            } else if ((c == p1 -> order) && (c < p2 -> order)) {   /* only set output carry */
               carry = tmerge(p1 -> T, carry);
               c = p1 -> order + 1;
               q = p1; p1 = p1 -> next; free(q);
            } else if ((c < p1 -> order) && (c == p2 -> order)) {   /* only set output carry */
               carry = tmerge(p2 -> T, carry);
               c = p2 -> order + 1;
               q = p2; p2 = p2 -> next; free(q);
            } else {                                                /* set tree and output carry */
               p -> next = (heap)malloc(sizeof(hnode));
               p = p -> next;
               p -> order = c;
               p -> T = carry;
               carry = tmerge(p1 -> T, p2 -> T);
               ++c;
               q = p1; p1 = p1 -> next; free(q);
               q = p2; p2 = p2 -> next; free(q);
            }
         }
      }
   }
   if (carry) {
      p -> next = (heap)malloc(sizeof(hnode));
      p = p -> next;
      p -> order = c;
      p -> T = carry;
      carry = NULL;
   }
   p -> next = NULL;
   return H;
}

heap insert ( heap H, int d, int v )
{
   heap H1;

   H1 = (heap)malloc(sizeof(hnode));
   H1 -> next = (heap)malloc(sizeof(hnode));
   H1 -> next -> next = NULL;
   H1 -> next -> order = 0;
   H1 -> next -> T = (tree)malloc(sizeof(tnode));
   H1 -> next -> T -> L = H1 -> next -> T -> R = NULL;
   H1 -> next -> T -> degree = d;
   H1 -> next -> T -> vertex = v;
   return hmerge(H,H1);
}

/*** Linear-time divide-and-conquer make heap ***/
heap makeheap ( int *D, int i, int j )
{
   heap H;
   int k;

   if (i >= j) {
      H = (heap)malloc(sizeof(hnode));
      H -> next = NULL; 
      if (i > j) return H;
      return insert(H,D[i],i);
   }
   k = (i + j)/2;
   return hmerge(makeheap(D,i,k), makeheap(D,k+1,j));
}

heap findmax ( heap H )   /* returns a pointer to the "previous" node */
{
   heap p, maxp;
   int max;

   if (H == NULL) {
      fprintf(stderr, "*** Error: Invalid heap in findmax...\n");
      exit(4);
   }
   if (H -> next == NULL) return NULL;
   p = H; max = -1; maxp = NULL;
   while (p -> next != NULL) {
      if (p -> next -> T -> degree > max) {
         max = p -> next -> T -> degree;
         maxp = p;
      }
      p = p -> next;
   }
   return maxp;
}

heap delmax ( heap H )
{
   heap H1, p, q;
   tree t;
   int i;

   if (H == NULL) {
      fprintf(stderr, "*** Error: Invalid heap in delmax...\n");
      exit(5);
   }
   q = findmax(H);
   if (q == NULL) {
      fprintf(stderr, "*** Error: Delete from empty heap...\n");
      exit(6);
   }
   i = q -> next -> order - 1;
   t = q -> next -> T -> L;
   H1 = (heap)malloc(sizeof(hnode));
   H1 -> next = NULL;
   while (i >= 0) {
      p = (heap)malloc(sizeof(hnode));
      p -> order = i;
      p -> T = t;
      t = t -> R;
      p -> T -> R = NULL;
      --i;
      p -> next = H1 -> next;
      H1 -> next = p;
   }
   free(q -> next -> T);
   p = q -> next;
   q -> next = p -> next;
   free(p);
   return hmerge(H,H1);
}

graph gengraph ( int n, heap H )
{
   graph G;
   int i, j, u, v, d, d1;
   heap p, H1;

   G = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      G[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) G[i][j] = 0;
   }
   p = findmax(H);
   while (p != NULL) {
      u = p -> next -> T -> vertex;
      d = p -> next -> T -> degree;
      H = delmax(H);
      H1 = (heap)malloc(sizeof(hnode));
      H1 -> next = NULL;
      for (i=0; i<d; ++i) {
         p = findmax(H);
         v = p -> next -> T -> vertex;
         d1 = p -> next -> T -> degree - 1;
         G[u][v] = G[v][u] = 1;
         if (d1) H1 = insert(H1,d1,v);
         H = delmax(H);
      }
      H = hmerge(H,H1);
      p = findmax(H);
   }
   return G;
}

int *getdegseq ( graph G, int n )
{
   int *D, i, j;

   D = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      D[i] = 0;
      for (j=0; j<n; ++j) if (G[i][j]) ++D[i];
   }
   return D;
}

int verify ( int *D, int *E, int n )
{
   while (--n >= 0) if (D[n] != E[n]) return 0;
   return 1;
}

int main ( int argc, char *argv[] )
{
   int n, *D, *E;
   heap H;
   graph G;

   srand((unsigned int)time(NULL));
   if (argc == 1) {
      printf("Number of vertices = "); scanf("%d", &n);
   } else {
      n = atoi(argv[1]);
   }
   D = genrandseq(n);
   if (!isgraphic(D,n)) {
      fprintf(stderr, "*** Error: The sequence is not graphic...\n");
      exit(1);
   }
   printf("+++ Degree sequence is graphic...\n");
   H = makeheap(D,0,n-1); printf("+++ Degree sequence stored in heap...\n");
   G = gengraph(n,H); printf("+++ Graph generated...\n");
   E = getdegseq(G,n);
   printf("+++ Correctness%sverified...\n", verify(D,E,n) ? " " : " NOT ");
   exit(0);
}