### OneWhoKnocks's blog

By OneWhoKnocks, history, 7 days ago, , 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. #dfs, Comments (1)
 » 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.