/* Implementation of Tarjan's algorithm for computing strongly connected
   components in a directed graph */

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

typedef struct _node {
   int nbr;
   struct _node *next;
} node;

typedef struct _header {
   int dfsno;
   int dfslo;
   int presentinstack;
   int compid;
   node *adjlist;
} header;

typedef header *graph;

graph gengraph ( int n, int m )
{
   int e, u, v;
   node *p, *q, *r;
   graph G;

   G = (header *)malloc(n * sizeof(header));
   for (u=0; u<n; ++u) {
      G[u].dfsno = -1;
      G[u].dfslo = -1;
      G[u].presentinstack = 0;
      G[u].compid = -1;
      G[u].adjlist = NULL;
   }
   e = 0;
   while (e < m) {
      u = rand() % n; do v = rand() % n; while (v == u);
      // scanf("%d%d", &u, &v);
      q = NULL; p = G[u].adjlist;
      while (p) {
         if (p -> nbr >= v) break;
         q = p; p = p -> next;
      }
      if ((p) && (p -> nbr == v)) continue;
      r = (node *)malloc(sizeof(node));
      r -> nbr = v;
      r -> next = p;
      if (q) q -> next = r; else G[u].adjlist = r;
      if (e % 9 == 0) printf("    ");
      printf("%2d %-2d   ", u, v);
      ++e;
      if (e % 9 == 0) printf("\n");
   }
   if (e % 9) printf("\n");
   return G;
}

void prngraph ( graph G, int n )
{
   int u;
   node *p;

   for (u=0; u<n; ++u) {
      printf("    %-3d->", u);
      p = G[u].adjlist;
      while (p) {
         printf(" %2d", p -> nbr);
         p = p -> next;
      }
      printf("\n");
   }
}

void freegraph ( graph G, int n )
{
   int u;
   node *p, *q;

   for (u=0; u<n; ++u) {
      p = G[u].adjlist; q = NULL;
      while (p) {
         q = p;
         p = p -> next;
         free(q);
      }
   }
   free(G);
}

void DFS ( graph G, int u, int *S, int *top, int *dfsno, int *ncomp )
{
   node *p;
   int v;

   S[++(*top)] = u;
   G[u].dfsno = G[u].dfslo = *dfsno;
   G[u].presentinstack = 1;
   ++(*dfsno);
   p = G[u].adjlist;
   while (p) {
      v = p -> nbr;
      if (G[v].dfsno < 0) {
         DFS(G,v,S,top,dfsno,ncomp);
         if (G[v].dfslo < G[u].dfslo) G[u].dfslo = G[v].dfslo;
      } else if (G[v].presentinstack) {
         if (G[v].dfsno < G[u].dfslo) G[u].dfslo = G[v].dfsno;
      }
      p = p -> next;
   }
   if (G[u].dfsno == G[u].dfslo) {
      printf("--- Component %2d:", *ncomp);
      while (1) {
         v = S[*top]; --(*top);
         printf(" %2d", v);
         G[v].presentinstack = 0;
         G[v].compid = *ncomp;
         if (v == u) break;
      }
      printf("\n");
      ++(*ncomp);
   }
}

int findcomp ( graph G, int n )
{
   int *S, u, dfsno, top, ncomp;

   S = (int *)malloc(n * sizeof(int));
   u = dfsno = 0; top = -1; ncomp = 0;
   while (u < n) {
      if (G[u].dfsno >= 0) { ++u; continue; }
      DFS(G,u,S,&top,&dfsno,&ncomp);
   }
   free(S);
   return ncomp;
}

/* Consider the component graph C of G constructed as follows. Collapse
   the vertices in each SCC of G to a single vertex of C. For two different
   components i and j, give a directed link from i to j in C if and only if
   there is a directed link fron vertex u to vertex v in G such that
   u belongs to Component i, and v to Component j. The essential
   components are those whose in-degrees are zero in C. The following
   function implements this observation, but without explictly creating
   the component graph C of G.
*/
int findesscomp ( graph G, int n, int c )
{
   int *isessential, i, j, u;
   node *p;

   isessential = (int *)malloc(c * sizeof(int));
   for (i=0; i<c; ++i) isessential[i] = 1;
   for (u=0; u<n; ++u) {
      i = G[u].compid;
      p = G[u].adjlist;
      while (p) {
         j = G[p -> nbr].compid;
         if (i != j) isessential[j] = 0;
         p = p -> next;
      }
   }

   u = 0;
   for (i=0; i<c; ++i) if (isessential[i]) {
      ++u;
      printf("--- Component %2d is essential\n", i);
   }
   free(isessential);
   return u;
}

int main ( int argc, char *argv[] )
{
   int n, m, c, ec;
   graph G;

   if (argc >= 3) { n = atoi(argv[1]); m = atoi(argv[2]); }
   else scanf("%d%d", &n, &m);
   printf("    n = %d\n    m = %d\n", n, m);
   srand((unsigned int)time(NULL));

   G = gengraph(n,m);
   printf("\n+++ The input graph\n"); prngraph(G,n);

   printf("\n+++ The components are\n");
   c = findcomp(G,n);

   printf("\n+++ The essential components are:\n");
   ec = findesscomp(G,n,c);
   printf("    Count = %d\n", ec);

   freegraph(G,n);

   exit(0);
}