// program to find biconnected components of a graph.
#include<iostream.h>
#include<conio.h>
class biconnected
{
private:
int a[10][10],n;
struct edge
{
int sv;
int tv;
};
typedef struct edge ed;
ed stack[20];
int top;
int dfn[10],l[10],num;
public:
biconnected();
void bicomp(int u,int v);
void setdata();
};
biconnected :: biconnected()
{
int i;
for(i=0;i<=10;i++)
{
dfn[i]=0;
l[i]=0;
}
num=1;
}
void biconnected::setdata()
{
int i,j;
cout<<"\nEnter number of vertices: ";
cin>>n;
cout<<"\nEnter Adjacency matrix: \n";
for(i=1;i<=n;i++)
{
cout<<"\nEnter "<<i<<" row: ";
for(j=1;j<=n;j++)
cin>>a[i][j];
}
}
void biconnected::bicomp(int u,int v)
{
int w,x,y;
dfn[u]=num;
l[u]=num;
num++;
for(w=1;w<=n;w++)
{
if(a[u][w]==1)
{
if((v!=w) && (dfn[w]<dfn[u]))
{
top++;
stack[top].sv=u;
stack[top].tv=w;
}
if(dfn[w]==0)
{
bicomp(w,u);
if(l[w]>=dfn[u])
{
cout<<"\nNew bicomponent\n\t\t";
do
{
x=stack[top].sv;
y=stack[top].tv;
top--;
cout<<x<<"---"<<y<<"\n\t\t";
}while(! ((x==u && y==w)||(x==w && y==u)) );
}
l[u]=l[u]>l[w]?l[w]:l[u];
}
else if(w!=v)
{
l[u]=l[u]>dfn[w]?dfn[w]:l[u];
}
}
}
}
void main()
{
biconnected b;
clrscr();
b.setdata();
b.bicomp(1,0);
getch();
}