Graph - easy problem

In above question how bipartite matching can be used to get answer?Can anybody explain bipartite matching algorithm?I know how to check whether graph is bipartite or not but don’t know about this bipartite matching.

How this matching algorithm can give answer to the above problem?
Help please , i am newbie in graph topic

thanks in advance :slight_smile:

Because you said you are a newbie in graphs, the problem can be solved even without that. Thinking about bipartite matching for this just helps visualizing the problem in a good manner, we want to classify all the vertices in two sets such that every vertex in first set connects only one unique vertex in other.

For doing it without matching, start from the source ( the first unvisited vertex). Get one of its neighbour (or adjacent node). Assume these two nodes make one edge where the two nodes have degree one. Find the next unvisited node and recur for this new vertex now. In the end if we are not left with any unvisited nodes, that states our matching in recursive calls are correct.

You may refer to this idea here.

1 Like

@damn_me can you explain in more detail , the dfs you modified i didn’t get that.So can you explain modified dfs in more detail? :slight_smile: