if the adjacent position is 1 we can traverse through that element and we can form a graph.So the number of graphs that we can form is 2.The solution for this question is very simple . Check every element in the matrix and if the element is 1 increase the count by 1 and change its connected elements (or nodes) to 0 .
Code: (in C)
int find_no_of_graphs(int** array,int rows,int cols)
{
int i,j,count=0;
for(i=0;i < m;i++)
{
for(j=0;j < n;j++)
{
if(array[i][j]==1)
{
//if the element is 1 increment the graph count and set it's connected elements to 0.
find_connected_positions(array,i,j);
count++;
}
}
}
return count;
}
void find_connected_positions(int** array,int i,int j,int rows ,int cols)
{
array[i][j]=0;
if(i-1>=0)
{
if(array[i-1][j]==1)
find_connected_positions(array,i-1,j,rows,cols);
if(j-1>=0)
{
if(array[i-1][j-1]==1)
find_connected_positions(array,i-1,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i-1][j+1]==1)
find_connected_positions(array,i-1,j+1,rows,cols);
}
}
if(i+1 < rows)
{
if(array[i+1][j]==1)
find_connected_positions(array,i+1,j,rows,cols);
if(j-1>=0)
{
if(array[i+1][j-1]==1)
find_connected_positions(array,i+1,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i+1][j+1]==1)
find_connected_positions(array,i+1,j+1,rows,cols);
}
}
if(j-1>=0)
{
if(array[i][j-1]==1)
find_connected_positions(array,i,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i][j+1]==1)
find_connected_positions(array,i,j+1,rows,cols);
}
}
Please let me know if there is any bug in the above code and your suggestions are always welcome .
No comments:
Post a Comment