LEGO  Lego
It's Christmas morning, and you've got what you wanted: a box of Lego™! (Okay, maybe not, but better than nothing)
Lego is pretty fun to tinker with, and you've decided to build some sort of shape.
(For the sake of this problem, let's say your shape is basically 2dimensional  it'll be a slab)
But once you pick it up, you discover that you didn't plan it properly, and your wonderful shape just falls apart.
Now, you're planning to build something big, and so you're going to use the computer to help you.
Write a program, that given the layout of a Lego design, outputs the number of pieces it would break into if picked up.
(Assume that the bricks bind together perfectly)
The Legos will be built on a xy coordinate plane, with (0,0) being the bottom left corner.
The blocks are flat on your carpet, so a block will never 'fall down'.
(If you haven't seen a Lego brick before: A Lego brick has grooves on its top that match with notches on the bottom.
If a groove and a notch bind, the bricks will stay together. See the diagram.
A brick will bind with another brick securely even if just a single notch touches another groove.
Input:
The first line contains N (the number of Lego pieces), 1 ≤ N ≤ 100000.
N lines follow, each with 4 integers x_{1}, y_{1}, x_{2}, y_{2} (0 ≤ x_{1} < x_{2} ≤ 2×10^{9}, 0 ≤ y_{1} < y_{2} ≤ 2×10^{9})
This means that there is a brick with bottom left corner (x_{1},y_{1}) and top right corner (x_{2},y_{2}). x denotes the horizontal coordinate and y the vertical coordinate. Two bricks will bind if one's bottom ycoordinate coincides with the other's top ycoordinate and the intersection of the two intervals (the bottom of one and the top of the other) has nonzero length.
No bricks will overlap.
Output:
A single line containing the number of separate pieces that these blocks form.
Sample Input:
4 0 0 2 2 1 2 3 4 2 0 4 2 4 0 6 2
Sample Output:
2
Explanation
Blocks #1,2,3 are joined securely.
However, #4 is just hanging around.
hide comments
kanishk779:
20190324 14:29:15
How should we construct the graph? 

luka_dzimba911:
20190315 16:12:00
Dont think too much, try to think of simple solution :D


Sajal Sarkar:
20161228 11:02:23
Did someone solve this question via counting connected component?


SANYAM JAIN:
20160803 19:01:48
Finally solved it, took so many wa and tle. 

lalitesh:
20160802 20:55:23
After WA n TLE , got AC ;) 

Liquid_Science:
20160801 09:54:30
AC in a go , but took me a lot of time though! :/ 

Shubham Sinha:
20160528 22:38:29
dsu rocks !! 

shikhar0037:
20160526 03:40:31
Nice problem . AC in 1 GO :) Last edit: 20160526 14:54:26 

birdie:
20150220 10:53:27
i am getting wa.. any tricky testcase ? 

shakaal:
20150120 06:12:09
please explain test case it snot clear 
Added by:  Brian Bi 
Date:  20090410 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Hanson Wang 