// This is a assignment to find the Strongly Connected Components from a Directed Graph

// The Code Efficiency of this program will not satisfy the corporate software builder.

// This Program is compiled by Dev-C++ 4.9.4.0.

// for further information please contact with:

//         Bappi Nath

//         ID: 01201026

//         Fall'01

//         Computer Science and Engineering

//         BRAC University

//         Cell: 88-018111757

//         email: bappinath@hotmail.com

 

 

 

#include<stdio.h>

#include<conio.h>

#include<string.h>

 

 

////some global variable

int len,count=0,neel_nod=0;

char arr[1024][1024],que[1024],black[1024],cycle[1024];

 

///general declaration of some function

void QueIn(char c);

char QueOut();

void Do_Black(char c);

int Already_Black(char c);

void Do_Black(char c);

int Check_Size();

void PrintStatus();

int NumberOfComponents();

void Seperate_Components(char c);

 

 

//body of QueIn(char c) func

void QueIn(char c)

{

int size=0;

for(;;)

    {

    if(que[size]=='#') break;

    size++;

    }

que[size]=c;

 

que[size+1]='#';

}

 

 

///body of QueOut() func

char QueOut()

{

char temp=que[0];

int i = 0;

for(;;)

    {

    que[i]=que[i+1];

    if(que[i+1]=='#') break;

    i++;

    } 

Do_Black(temp); 

return temp;

}

 

///body of Already_Black(char c) func

int Already_Black(char c)

{

int size=0;

while(black[size]!='#')

    {

    if (black[size]==c) return 1;

    size++;

    }

return 0;

}

 

///body of Do_Black(char c) func

void Do_Black(char c)

{

int size=0;

while(black[size]!='#')

    {

    size++;

    }

black[size]= c;

black[size+1]= '#';   

}

 

///body of Check_Size() func

int Check_Size()

{

int i=0;

while(black[i]!='#')

      {

      i++;

      }

 

return i;

}

 

////body of func Already_Exist_In_Que(char c)

int Already_Exist_In_Que(char c)

{

int size=0;

while(que[size]!='#')

    {

    if (que[size]==c) return 1;

    size++;

    }

return 0;

 

}

 

 

 

////////body of print function

void PrintStatus()

{

int i,j;

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

    {

        for(j=0;j<=len;j++)

            {

            printf("%c ",arr[i][j]);

            }

        printf("\n");

    }

printf("\n\n");

}

 

 

////here is the body of void Seperate_Components() func

void Seperate_Components(char c)

{

 

int i=0;

while(black[i]!=c)

         {

         i++;

         }

 

while(black[i]!='#')

         {

         cycle[neel_nod]=black[i];

         i++;

         neel_nod++;    

         }            

      

cycle[neel_nod]='#';

neel_nod++;

 

}

 

///here is the body of NumberOfComponents() func

 

int NumberOfComponents()

{

black[0]='#';

que[0]='#';

int i=1,j;

char Out_from_Que;

QueIn(arr[1][0]);

 

while(Check_Size()!=len)

        {

       

        Out_from_Que=QueOut();

       

        printf("\n%c",Out_from_Que);

        i=1;

        while(arr[i][0]!=Out_from_Que)

               {

               i++;

               }

      

        for(j=1;j<=len;j++)

                {

                if(arr[i][j]=='1')

                     {

                    

                     if(Already_Black(arr[0][j])==1)

                              {

                              Seperate_Components(arr[0][j]);

                              count++;

                              }

                     

                    

                    

                     if(Already_Black(arr[0][j])==0 && Already_Exist_In_Que(arr[0][j])==0)

                              {

                              QueIn(arr[0][j]);

                              }

                              

                    

                    

                     }

               

                }

       

        }///end of the while loop

        if(neel_nod!=0)

                {

                cycle[(neel_nod-1)]='$';

                }else

                {cycle[neel_nod]='$';

                }

 

 

return count;

}

 

 

 

 

 

int main()

{

 

///////////////////build the array according to lebeling////////////////////////////////

int i,j;

char lebel[1024];

 

printf("\t\t  ----------------------------------");

printf("\n\n\t\t\t Algorithm (CSE 221)\n");

printf("\t\t     Take Home Lab Assignment: 03\n\n");

printf("\t\t  ----------------------------------\n");

printf("\t\t\t\t Prepared by:\n");

printf("\t\t\t\t\t      Promila Kanti Nath\n");

printf("\t\t\t\t\t      ID:01201026\n");

printf("\t\t\t\t\t      Computer Science & Engineering\n");

printf("\t\t\t\t\t      BRAC University.\n\n\n\n");

 

printf(" Input The Graph G by Adjacent Matrix:\n");

printf("______________________________________\n\n");

printf(" Enter the lebel of the vertices without seperatiing by space: ");

 

scanf("%s",&lebel);

 

len=strlen(lebel);

 

 

 

/////////////////implimentation////////////////////

 

int k;

for(k=1;k<=len;k++)

{

            arr[k][0]=lebel[k-1];

 

}

 

for(k=1;k<=len;k++)

{

            arr[0][k]=lebel[k-1];

}

///////////////////////initilize by zero/////////////////////

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

{

    for(j=1;j<=len;j++)

    {

        arr[i][j]='0';

    }

   

}

 

//////////////////////////////////////////////////////////

 

 

//////////////////////////print the current status///////////////////////

 

 

printf("\n\nThis is the current situation of the Adjacency Matrix: \n\n\n");

PrintStatus();

 

/////////////////////////////////////////////////////////////////////////////

 

 

////////////////get the value//////////////////

char ch='y';

 

while(ch=='y')

{

printf("\n\nPlease, Enter the Row and Colomn that have value One: ");

scanf("%d %d",&i,&j);

arr[i][j]='1';

printf("\nDo u wanna enter any more?(y/n) :");

ch=getche();

}

 

 

//////print the current status//////

 

printf("\n\nThis is the current situation of the Adjacency Matrix: \n\n\n");

PrintStatus();

 

 

/////here we start the find program for strongly connected components

 

printf("\n\n\n Answer To The Problem Statement: A\n");

printf("_____________________________________\n\n");

int Number_Of_Components = NumberOfComponents();

printf("\n\nTotal Number of Strongly Connected Component(s): %d",Number_Of_Components);

printf("\n\nThe Components are given bellow:\n\n");

k=0;

while(cycle[k]!='$')

        {

        if(cycle[k]!='#')

                {

                 printf("%c",cycle[k]);

                }else

                printf("\n");

        k++;

        }

getch();

}