Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.

Explanation:

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.

/*CODE*/

#include<stdio.h>
#define SIZE 1010
void disable_connected(int i, int j);
int matrix[SIZE][SIZE]={0};

main()
{
int t,size,i,j,k,num_connected=0;

    scanf("%d",&t);
    while(t)
    {
        t--;
        num_connected = 0;
        scanf("%d",&size);
        for(i=0;i<=size+1;i++)
        {
            matrix[0][i] = matrix[size+1][i]= matrix[i][0] = matrix [i][size+1] = 0;
        }
        for(i=1;i<=size;i++)
        {
            for(j=1;j<=size;j++)
            {
                scanf("%d",&matrix[i][j]);
            }
        }

        for(i=1;i<=size;i++)
        {
            for(j=0;j<=size;j++)   
            {
                if(matrix[i][j] == 1)
                {
                    disable_connected(i,j);
                    num_connected++;
                }
            }
        }
        printf("%d\n",num_connected);
    }

return 0;
}

void disable_connected(int i, int j)
{
int p,q;
       
    matrix[i][j] = 2;
    for(p=i-1;p<=i+1;p++)
    {
        for(q=j-1;q<=j+1;q++)
        {
            if(matrix[p][q] == 1)
            {
                matrix[p][q] =2;
                disable_connected(p,q);
            }
        }
    }

return ;
}

COUNTING SORT

/* Program for Counting sort on numbers whose values are in certain boundary */

#include<stdio.h>
#include<stdlib.h>
#define N 100
#define LOWER_BOUND 30
#define UPPER_BOUND 99
void counting_sort(int *list,int size);

main()
{
int i=0,list[N];
int key,size;

    printf("Enter numbers with-in range %d-%d and stop with -9999\n",LOWER_BOUND,UPPER_BOUND);
    do
    {
        scanf("%d",&key);
        if(key == -9999)
        {
            break;
        }
        else if((key < LOWER_BOUND) || (key > UPPER_BOUND))
        {
            printf("Enter a value in the range %d-%d\n", LOWER_BOUND, UPPER_BOUND);
        }
        else
        {
            list[i++] = key;
        }
    }while(1);
    size = i;
    printf("original \n");

    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }

    printf("\nSorted  \n");
    counting_sort(list,size);
    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }
    getchar();
    getchar();
    return 0;
}

/* This function does the counting sort */
void counting_sort(int *list, int size)
{
int i,j,k,count[UPPER_BOUND-LOWER_BOUND+1] = {0};

    /* Count the number of repetetions for each number entered */
    for(i=0;i<size;i++)
    {
        count[list[i]-LOWER_BOUND]++;
    }
    k=0;
    /* Fill the array according to the count */
    for(i=0;i<(UPPER_BOUND-LOWER_BOUND+1);i++)
    {
        if(count[i] !=0)
        {
            for(j=0;j<count[i];j++)
            {
                list[k++] = i+LOWER_BOUND;
            }
        }
    }
    return;
}

QUICK SORT

/* QUICK sort is the fastest algorithm on random data of O(n log n) */

#include<stdio.h>
#include<stdlib.h>
#define N 100
void quick_sort(int *list,int start, int end);

main()
{
int i=0,list[N];
int key,size=1;

    do
    {
        scanf("%d",&key);
        if(key == -9999)
        {
            break;
        }
        else
        {
            list[i++] = key;
        }
    }while(1);
    size = i;
    printf("original \n");

    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }

    printf("\nSorted  \n");
    quick_sort(list,0,size-1);
    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }
    getchar();
    getchar();
    return 0;
}

/* This function does the quick sort recursively */
void quick_sort(int *list, int start,int end)
{
int i,j, pivot,temp;
/* Algo should end if start > = end*/
    if(start<end)
    {
        /* store pivot and indexes*/
        pivot = list[end];
        i=start;
        j=end-1;
        while(i<j)
        {
            /* move i until list[i] < pivot*/
            while(list[i] < pivot)
            {
                i++;
            }
            /* move j until list[j] > pivot */
            while( (i < j) &&(list[j] > pivot))
            {
                j--;
            }

            /* interchange if required*/
            if(i<j)
            {
                temp    = list[i];
                list[i] = list[j];
                list[j] = temp;
                i++;
                j--;
            }
        }
        /* partition is done at i. move the pivot to i*/
        if(i<end)
        {
            list[end] = list[i];
            list[i]   = pivot;
        }
        /*Call recursive*/
        quick_sort(list,start,i-1);
        quick_sort(list,i+1,end);
    }
    return;
}

HEAP SORT

#include<stdio.h>

#define N 1000

void build_heap(int *a,int size,int key);

int heap_delete(int *a,int size,int key);

int main()

{

int a[N],b[N],key,choice;

int i,size=0;

int result;

printf("Enter numbers followed by -9999 to stop \n");

for(i=0;;i++)

{

scanf("%d",&key);

if(key==-9999)

{

break;

}

build_heap(a,i,key);

}

size=i;

printf("heaped size %d \n",size);

for(i=1;i<=size;i++)

{

printf("%d ",a[i]);

}

while(1)

{

printf("\nEnter\n1 - ADD \n2 - Delete \n3 - Sort \n0 - Exit\n");

scanf("%d",&choice);

if(choice == 3)

{

printf("sorted \n");

for(i=1;i<=size;i++)

{

b[i]=a[i];

}

for(i=0;i<size;i++)

{

printf("%d ",b[1]);

heap_delete(b,size-i,b[1]);

}

}

else if(choice == 2)

{

printf("Enter the number to be deleted \n");

scanf("%d",&key);

result = heap_delete(a,size,key);

if(result)

size--;

printf("New heap \n");

for(i=1;i<=size;i++)

{

printf("%d ",a[i]);

}

}

else if (choice == 1)

{

printf("Enter the number to be Added \n");

scanf("%d",&key);

build_heap(a,size,key);

size++;

printf("New heap \n");

for(i=1;i<=size;i++)

{

printf("%d ",a[i]);

}

}

else

{

break;

}

}

return 0;

}

void build_heap(int *a,int size,int key)

{

int i,j,temp;

/*Add element to the end*/

a[size+1]=key;

j=size+1;

/*Adjust the heap by moving the new element to right position */

while(j>1 && a[j] > a[j/2])

{

temp = a[j];

a[j] = a[j/2];

a[j/2] = temp;

j=j/2;

}

return;

}

int heap_delete(int *a,int size,int key)

{

int i,j,temp;

/*Return if heap size is zero */

if(size == 0)

return 0;

for(i=1;i<=size;i++)

{

if(key==a[i])

{

/* Replace the deleted element with the

last element in the Heap */

a[i]=a[size];

/*store the element at the end*/

a[size] = key;

break;

}

}

/*Return if Key is not found*/

if(i == size+1)

{

printf(" Key not available \n");

return 0;

}

j=i*2;

/*Adjust the heap*/

while(j < size)

{

/* move to the greater leaf */

if ((j < size-1) && (a[j]<a[j+1]))

j++;

if(a[j/2] < a[j])

{

temp = a[j/2];

a[j/2] = a[j];

a[j] = temp;

j= j*2;

}

else

{

break;

}

}

return 1;

}

MERGE SORT

/*
 * Merge Sort -
 * This is recursive function
 * O(n log(n))
  */


void merge_sort(int *list,int start,int end)
{
   /* recursing should be stoppped if start > end */
    if(start<end)
    {
        /* swap for merging two elements*/
        if(end-start == 1)
        {
            if(list[start]>list[end])
            {
                list[end]   = list[end] ^ list[start];
                list[start]   = list[end] ^ list[start];
                list[end] = list[end] ^ list[start];
            }
        }
        else
        {

            merge_sort(list,start, (start+end)/2);
            merge_sort(list,(start+end)/2+1,end);
            merge(list,start,(start+end)/2,end);
        }
    }
}

/*
 * Function to merge two arrays
 * To avoid memory wastage malloc used. Otherwise array of max size can be used
 */
void merge(int *list,int start,int middle,int end)
{
    int i,j,k,l;
    int *temp; /* if not dynamic max size should be used*/

    temp = (int *)malloc(sizeof(int)*(end-start+1));
    i=start;
    j=middle+1;
    k=0;
    while(1)
    {
       /* store the small element into temp array*/
        if(list[i]<list[j])
        {
            temp[k++]=list[i++];
        }
         else
        {
            temp[k++] = list[j++];
        }
      /* Check if any of the arrays are finished. If so append the other array*/
        if(i>middle)
        {
            for(;j<=end;j++)
                temp[k++]=list[j];
            break;
        }
        else if(j>end)
        {
            for(;i<=middle;i++)
                temp[k++]=list[i];
            break;
        }
    }
   /*  Fill the original array with merge sorted*/
    k=0;
    for(i=start;i<=end;i++)
    {
        list[i]=temp[k++];
    }

}

REVERSE LINKS IN LINKED LIST

/ * 

  *Reverse a linked list

  * This program reverse the links in a linked list. but not the data.

  */

void reverse_link(NODE **root)

{

    NODE *p,*q,*r=NULL;

    if(*root == NULL)

        return;

    p=*root;

    if(p->next != NULL)

    {

        q=p->next;

        p->next = NULL;

        while(q!=NULL)

        {

            r=q->next;  /* First store the next link address */

            q->next=p; /*  Reverse the link */

            p=q;           /* Move forward */

            q=r;

        }

        *root = p;  /* root is at last node */

    }

    return;

}

INSERTION SORT

/* Insertion Sort is simplest in-place sort algorithm to sort an array*/

 /* The code for the algorithm is as given below */


void insertion_sort(int *list, int size)
{
    int i,j;

    for(i=1;i<size;i++)
    {
        for(j=i;j>0;j--)
        {
            if(list[j]>list[j-1])
            {   /* SWAP */
                list[j]   = list[j]^list[j-1];
                list[j-1] = list[j]^list[j-1];
                list[j]   = list[j]^list[j-1];
            }
            else
            {
                break;
            }
        }
    }
return;
}