#include<iostream>
#include <conio.h>
#include <cstdlib>
using namespace std;
bool isconnected(const int* const *const ,int);
bool isconnect(const int *const*const,int,int,int,int*const);
int* fill(int*const,int,int);
bool exist(const int*const,int,int);
int findlen(const int*const*const,int,int,int,int*const);
int main()
{
int n,**p;
cout<<"enter count of vertex:";
cin>>n;
p=new int*[n];
for(int i=0;i<n;++i)
p[i]=new int[n];
cout<<endl<<"enter matrix of connected graph."<<endl;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cin>>p[i][j];
if(!isconnected(p,n))
cout<<"graph is not connected.";
else
{
int d=0,*stack=new int[n];
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
fill(stack,n,-1);
int m=findlen(p,n,i,j,stack);
cout<<i<<"-->"<<j<<" = "<<m<<endl;
d=d>m?d:m;
}
cout<<endl<<endl<<"diameter ="<<d<<endl;
delete []stack;
}
for(int i=0;i<n;++i)
delete []p[i];
delete []p;
getch();
return 0;
}
bool isconnected(const int*const*const matrix,int row)
{
int*stack=new int[row];
for(int i= 0;i<row;++i)
for(int j=i+1;j<row;++j)
{
if(!isconnect(matrix,row,i,j,fill(stack,row,-1)))
return false;
}
return true;
}
bool isconnect(const int*const*const m,int row,int a,int b,int*const stack)
{
if(m[a][b])
return true;
for(int i=0,j;i<row;i++)
{
if(m[a][i]&&!exist(stack,row,i))
{
for(j=0;stack[j]!=-1;++j);
stack[j]=i;
if(isconnect(m,row,i,b,stack))
return true;
}
}
return false;
}
int*fill(int*const a,int size,int value)
{
for(int i=0;i<size;++i)
a[i]=value;
return a;
}
bool exist(const int*const list,int size,int n)
{
for(int i=0 ; i < size && list[i]!=-1 ; ++i)
if(list[i]==n)
return true;
return false;
}
int findlen(const int * const * const M ,int n ,int A ,int B,int *const stack)
{
if(M[A][B])
return 1;
int len=n+1 , tmp;
for(int i=0,j; i < n ; ++i)
{
if(M[A][B] && ! exist(stack,n,i))
{
for(j=0 ; stack[j]!=-1 ; ++j);
stack[j]=i;
if(tmp=findlen(M,n,i,B,stack))
len=++tmp < len ? tmp : len;
stack[j]=-1;
}
}
return len==n+1? 0 : len;
}