// Compressed adjacency lists for a directed graph
// CSE 3318 Notes 13

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

int n;  // number of nodes
int m;  // number of edges
struct edge {
  int tail,head,type; 
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *tailTab;  // Table indicating first in range of edges with a common tail
int *headTab;  // Table with just the head vertex number for each edge.

// Reading the input file and organize adjacency lists

int tailThenHead(const void* xin, const void* yin)
// Used in calls to qsort() and bsearch() for read_input_file()
{
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 read_input_file()
{
int a,b,i,j;
edgeType work;
edgeType *ptr;

scanf("%d %d",&n,&m);
edgeTab=(edgeType*) malloc(m*sizeof(edgeType));
if (!edgeTab)
{
  printf("edgeTab malloc failed %d\n",__LINE__);
  exit(0);
}

for (i=0; i<m; i++)
{
  scanf("%d %d",&a,&b);
  if (a<0 || a>=n || b<0 || b>=n)
  {
    printf("Invalid input %d %d at %d\n",a,b,__LINE__);
    exit(0);
  }
  edgeTab[i].tail=a;
  edgeTab[i].head=b;
}

// sort edges
qsort(edgeTab,m,sizeof(edgeType),tailThenHead);

// Coalesce duplicates into a single edge
j=0;
for (i=1; i<m; i++)
  if (edgeTab[j].tail==edgeTab[i].tail
     && edgeTab[j].head==edgeTab[i].head)
    ; 
  else
  {
    j++;
    edgeTab[j].tail=edgeTab[i].tail;
    edgeTab[j].head=edgeTab[i].head;
  }
m=m ? j+1 : 0;  // Weird possibiity of no edges

// For each vertex as a tail, determine first in range of edgeTab/headTab entries.
// Also copy each edge's head vertex number to headTab
tailTab=(int*) malloc((n+1)*sizeof(int));
headTab=(int*) malloc(m*sizeof(int));
if (!tailTab || !headTab)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
j=0;
for (i=0; i<n; i++)
{
  tailTab[i]=j;
  for ( ;
       j<m && edgeTab[j].tail==i;
       j++)
    headTab[j]=edgeTab[j].head;
}
tailTab[n]=m;
}

void print_graph()
{
int i,j;

printf("tailTab\n");
for (i=0;i<=n;i++)
  printf("%d %d\n",i,tailTab[i]);

printf("headTab\n");
for (i=0;i<n;i++)
  for (j=tailTab[i];j<tailTab[i+1];j++)
    printf("%d %d (%d->%d)\n",j,headTab[j],i,headTab[j]);
}

int main ()
{
read_input_file();

print_graph();

free(edgeTab);
free(tailTab);
free(headTab);
}