Can you suggest me a solution for the problem sgu 369?
Vasya loves his new game which is played on an infinite rectangular grid where K cells are initially black, all other cells are white. The move of the game is to find three black cells which are vertices of some rectangle with sides parallel to coordinate axis such that the fourth vertex of the rectangle is white. In this case you need to paint the fourth vertex black. Vasya asks you to write a program which calculates the number of black cells in the end of the game, i.e. when no more moves can be made.
(0 ≤ K≤ 2· 10^5) and -10^9 ≤ Xi, Yi ≤ 10^9
Solution : It can be solved using disjoint set. Initially, all coordinates with same x coordinate are in same disjoint set. So if we will take two different x1, x2 coordinates, and there is some y coordinate so that (x1, y) and (x2, y) are black points, then x1 and x2 will be merged. Because if there is a point (x1, y1) then (x2, y1) will appeared.
Another solution : we can make a bipartite graph . One partite set is rows and another is columns , then if there is a black cell in position(x,y) , we add a edge from x'th row to y'th column.
For each connected component of graph we can paint all cells related to this component black . And we can't paint any other cell.
Answer for each connected component is (number of vertices in first partite set)*(number of vertices in second partite set) and answer to problem is sum of answers of it's connected component.