#include <stdio.h>
#include <string.h>
#include <search.h>

int numEdges,numVertices,nextVertexNumber=0;
int *tailHeader,*headTab;

struct edge {
  int tail,head;
};
typedef struct edge edgeType;
edgeType *edgeTab;
char **stringNameTable;

int name2number(char *x)
{
ENTRY e,*ep;

< Returns vertex number if name was previously inserted >

< Assigns next vertex number if name was not previously inserted >

}

void readInput()
{
int i;
char tailString[21],headString[21];

scanf("%d %d",&numVertices,&numEdges);
stringNameTable=(char**) malloc(numVertices*sizeof(char*));
if (!stringNameTable)
{
  printf("error 0\n");
  exit(0);
}
tailHeader=(int*) malloc((numVertices+1)*sizeof(int));
if (!tailHeader)
{
  printf("error 1\n");
  exit(0);
}

edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType));
headTab=(int*) malloc(numEdges*sizeof(int));
if (!edgeTab || !headTab)
{
  printf("error 2\n");
  exit(0);
}

if (!hcreate(numVertices))
{
  printf("error 3\n");
  exit(0);
}

for (i=0;i<numEdges;i++)
{
  scanf("%s %s",tailString,headString);
  edgeTab[i].tail=name2number(tailString);
  edgeTab[i].head=name2number(headString);
}

if (numVertices!=nextVertexNumber)
{
  printf("missing vertices\n");
  exit(0);
}
}

int tailThenHead(const void* xin, const void* yin)
/* Used in call to qsort() for buildAdjacencies() */
{
int result;
edgeType *x,*y;

x=(edgeType*) xin;
y=(edgeType*) yin;
result=x->tail - y->tail;
if (result!=0)
  return result;
else
  return x->head - y->head;
}

void buildAdjacencies()
{
/* Builds compact adjacency structure */
int duplicates=0,i,j,k;

qsort(edgeTab,numEdges,sizeof(edgeType),tailThenHead);

< Use edgeTab to build compact adjacency structure >

if (duplicates>0)
{
  printf("%d duplicates found & removed\n",duplicates);
  numEdges-=duplicates;
}
}

void dump()
{
int i,j;

printf(" i   stringNameTable[i]\n");
for (i=0;i<numVertices;i++)
  printf("%3d    %s\n",i,stringNameTable[i]);
printf(" i  tailHeader[i]\n");
for (i=0;i<=numVertices;i++)
  printf("%3d    %3d\n",i,tailHeader[i]);
printf(" i  headTab[i]\n");
for (i=0;i<numEdges;i++)
  printf("%3d    %3d\n",i,headTab[i]);
for (i=0;i<numVertices;i++)
{
  printf("tail vertex %s, head vertices are: ",stringNameTable[i]);
  for (j=tailHeader[i];j<tailHeader[i+1];j++)
    printf("%s ",stringNameTable[headTab[j]]);
  printf("\n");
}
}

int intCompare(const void* xin, const void* yin)
{
int *x,*y;

x=(int*) xin;
y=(int*) yin;
return (*x) - (*y);
}

int edgePresent(int tailNum,int headNum)
{
< This amounts to a call to bsearch on a small range of entries in headTab>
}

void testReflexive()
{
int i;

< Loops through vertices and checks for self-loop >
}

void testSymmetric()
{
int i,j;

< Navigates tailHeader[] & headTab.  Each edge is then checked for a reverse >
}

main()
{

readInput();
printf("buildAdjacencies()\n");
buildAdjacencies();
dump();
printf("testReflexive()\n");
testReflexive();
printf("testSymmetric()\n");
testSymmetric();
}