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

#define NROOMS 40
#define PROBIND 20

void genDoors ( int A[][NROOMS] )
{
   int i, j;

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

   for (i=0; i<NROOMS; ++i) {
      A[i][i] = 1;
      for (j=i+1; j<NROOMS; ++j) {
         A[i][j] = A[j][i] = (rand() % PROBIND) ? 0 : 1;
      }
   }
}

void printConn ( int A[][NROOMS] )
{
   int i, j;

   for (i=0; i<NROOMS; ++i) {
      for (j=0; j<NROOMS; ++j) printf("%d ",A[i][j]);
      printf("\n");
   }
   printf("\n");
}

void boolMul ( int A[][NROOMS], int B[][NROOMS], int C[][NROOMS] )
{
   int i, j, k;
   int D[NROOMS][NROOMS];

   for (i=0; i<NROOMS; ++i) {
      for (j=0; j<NROOMS; ++j) {
         D[i][j] = 0;
         for (k=0; k<NROOMS; ++k) {
            if (A[i][k] && B[k][j]) {
               D[i][j] = 1; break;
            }
         }
      }
   }

   for (i=0; i<NROOMS; ++i) for (j=0; j<NROOMS; ++j) C[i][j] = D[i][j];
}

void checkConn ( int A[][NROOMS] )
{
   int i, j, done[NROOMS];

   for (i=0; i<NROOMS; ++i) done[i] = 0;

   i = 0;
   while (i < NROOMS) {
      if (!done[i]) {
         j = i;
         while (j < NROOMS) {
            if (A[i][j]) {
               done[j] = 1; printf("%d ", j);
            }
            ++j;
         }
         printf("\n");
      }
      ++i;
   }
}

int main ()
{
   int A[NROOMS][NROOMS], len;

   /* Generate doors randomly */
   genDoors(A);

   printf("Initial connectivity:\n"); printConn(A);

   /* Compute connectivity via Boolean multiplication */
   len = 1;
   while (len < NROOMS-1) {
      boolMul(A,A,A);
      len *= 2;
   }

   printf("Final connectivity:\n"); printConn(A);

   /* Identify connected groups */
   checkConn(A);

   exit(0);
}