/* 4(a). W.A.P. to check whether the given graph is connected graph or not using Warshall's algorithm. */

#include<iostream.h>

#include<conio.h>

void main()

{

    int n,a[10][10],p[10][10],path=1;

    clrscr();

    cout<<"Enter the no of elements in the graph : ";

    cin>>n;

    cout<<"Enter the matrix of the graph :\n";

        for (int i = 0; i < n; i++) // To read the adjoint matrix

            for (int j = 0; j < n; j++)

            {

                cin>>a[i][j];

                p[i][j] = a[i][j];

            }

// Making the directed graph undirected

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

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

        if (p[i][j]) p[j][i] = 1;

// Applying Warshall's algorithm

for (int k = 0; k < n; k++)

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

        if (p[i][k])

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

                p[i][j] |= p[k][j];

                cout<<"\nGiven graph is verified & the matrix is as shown below :\n";

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

            {

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

                {

                    if (p[i][j] == 0) path = 0;

                        cout<<p[i][j]<<"\t";

                }

                cout<<"\n";

            }

            if (path)

                cout<<"\nGRAPH IS CONNECTED";

            else

                cout<<"\nGRAPH IS NOT CONNECTED";

                getch();

 }

/* OUTPUT

Enter the no of elements in the graph : 3

Enter the matrix of the graph :

1 0 1

0 1 0

1 1 0

Given graph is verified & the matrix is as shown below :

1 1 1

1 1 1

1 1 1

GRAPH IS CONNECTED

Enter the no of elements in the graph : 3

Enter the matrix of the graph :

1 0 1

0 1 0

0 0 1

Given graph is verified & the matrix is as shown below :

1 0 1

0 1 0

1 0 1

GRAPH IS NOT CONNECTED

*/