First ever graph problem

general
, ,
1

hello everyone,i have just started doing graph problems and i know dfs and bfs.I picked this problem BUGLIFE.I know how to print elements in dfs but don’t have idea how to modify dfs to make this question.can anybody please explain me this question in details,how to approach this.My solution done so far link ideone…its not complete because i am not getting how to go further.Looking forward for help.Thanks

2

Make an array such that a[i] keeps that of the gender of the ith bug. Now, assign a gender, like 0 to this bug is its gender isn’t already determined and for every bug is interacts with, assign to that bug the opposite opposite gender, 1 in this case.
If you come across a bug whose gender is to be assigned as 1 but is already determined, and opposite, 0 in this case, then this bug is suspicious.

Here is my solution : http://ideone.com/3hHuon

1 Like
3

Try understanding the problem first, (I didn’t in one go, or I should say many goes :P). A bug can have only two possible genders, lets say 1 and -1. So, you basically need to check whether in graph, all nodes are such that if two nodes are connected, one should be labelled as 1 and other should be -1. So, create here, an array that stores the value of gender for a particular node. Have a look at this code:

bool dfs(int src)
{
int tot = graph[src].size();
bool res=1;
for(int i=0;i<tot;i++)
{
	if(gender[src]== gender[graph[src][i]])  
     // if the source and child node have same gender, we simply return 0 here
	 return 0;
	 
	if(!gender[graph[src][i]])
	{
     // if not same, then I am assigning the gender of child node as opposite to that of the source node
		gender[graph[src][i]]=-1*(gender[src]); 
      // And is needed as the result needs to be true for the whole graph
		res= (res&dfs(graph[src][i]));
	}
}

return res;

}

In the main function, you need to take the return value and check if it’s true or false. If its true, then that means no bugs are there, other way round in the latter case, there are suspicious bugs.

1 Like
4

thanks(again)…i think it will take some time to get familiar

5

thanks a lot…

6

@doodle90 Anytime … :slight_smile: happy to help!!