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

#define NODECNT 100
#define ITERCNT 100
#define VERY_LARGE 1000000

typedef int **graph;

graph genrandgraph ( int n, double p )
{
   graph G;
   int u, v;

   G = (int **)malloc(n * sizeof(int *));
   for (u=0; u<n; ++u) {
      G[u] = (int *)malloc(n * sizeof(int));
      G[u][0] = 0;
   }
   for (u=0; u<n; ++u) for (v=u+1; v<n; ++v) {
      if (((double)rand() / (double)RAND_MAX) < p) {
         G[u][++G[u][0]] = v;
         G[v][++G[v][0]] = u;
      }
   }
   return G;
}

void freegraph ( graph G, int n )
{
   int u;

   for (u=0; u<n; ++u) free(G[u]);
   free(G);
}

/* BFS with a queue of size n */
int isconnected ( graph G, int n )
{
   int *visited, i, u, v, front, back, *queue;

   visited = (int *)malloc(n * sizeof(int));
   for (u=0; u<n; ++u) visited[u] = 0;

   queue = (int *)malloc(n * sizeof(int));
   queue[0] = 0; front = 0; back = 0; visited[0] = 1;
   while (back >= front) {
      u = queue[front]; ++front;
      for (i=1; i<=G[u][0]; ++i) {
         v = G[u][i];
         if (!visited[v]) {
            ++back; queue[back] = v;
            visited[v] = 1;
         }
      }
   }

   i = 1;
   for (u=0; u<n; ++u) if (!visited[u]) { i = 0; break; }

   free(visited);
   free(queue);

   return i;
}

int diameter ( graph G, int n )
{
   int **D, u, v, w, d;

   D = (int **)malloc(n * sizeof(int *));
   for (u=0; u<n; ++u) {
      D[u] = (int *)malloc(n * sizeof(int));
      for (v=0; v<n; ++v) D[u][v] = VERY_LARGE;
      D[u][u] = 0;
   }

   for (u=0; u<n; ++u) for (v=1; v<=G[u][0]; ++v)
      D[u][G[u][v]] = 1;

   for (w=0; w<n; ++w) {
      for (u=0; u<n; ++u) {
         for (v=0; v<n; ++v) {
            d = D[u][w] + D[w][v];
            if (d < D[u][v]) D[u][v] = d;
         }
      }
   }

   d = 0;
   for (u=0; u<n; ++u) for (v=0; v<n; ++v) if (D[u][v] > d) d = D[u][v];

   for (u=0; u<n; ++u) free(D[u]);
   free(D);

   return d;
}

int main ()
{
   graph G;
   int i, cnt;
   double dia;
   double p;

   srand((unsigned int)time(NULL));

   for (p=0.000; p <= 1.0001; p += 0.005) {
      cnt = 0; dia = 0;
      for (i=0; i<ITERCNT; ++i) {
         G = genrandgraph(NODECNT,p);
         cnt += isconnected(G,NODECNT);
         dia += diameter(G,NODECNT);
         freegraph(G,NODECNT);
      }
      if (cnt) dia = (dia - (double)VERY_LARGE * (double)(ITERCNT - cnt)) / cnt;
      else dia /= (double)ITERCNT;
      printf("%6.4lf %4.2lf %5.1lf\n", p, (double)cnt / (double)ITERCNT, dia);
   }
   exit(0);
}