Problem Statement:
There are n Coins present in a cartesian plane. We have been given coordinates(x,y) of these coins. We can take home as much of these coins possible, given constraint that no 2 coins should have either x or y coordinates in common. Find the maximum number of coins we can take back home.
My Approach:
For a particular coin with x and y coordinates, i added 2 vertices(x and y) having an edge between them. So, i was able to convert this problem to a graph problem which will be to find minimum number of vertices to be removed so that each vertex in the graph has an edge with only one other vertex.
I wanted to discuss the possible approaches to solve this problem. Thanks.
Ok, I'll try.
Construct a bipartite graph which 1 side is a set of nodes representing X-coordinates and the other side is the set of nodes representing Y-coordinates. An edge represents a coin.
According to the statement, you will pick maximum number of edges such that each node will be adjacent to at most 1 edge in the picked set. That is equivalent to the maximum matching of the graph.
Now it is a well-known problem.