Program to find biconnected components of a graph

// 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();
}
Chitra
Chitra

Leave a Reply

Your email address will not be published. Required fields are marked *

Get the latest updates on your inbox

Be the first to receive the latest updates from Codesdoc by signing up to our email subscription.

    StudentProjects.in