#K39717. Largest Connected Component
Largest Connected Component
Largest Connected Component
You are given n distinct points in the 2D plane, each represented by coordinates \( (x_i, y_i) \). Two points are considered connected if they share the same x-coordinate or the same y-coordinate. A connected component is a set of points in which any two points are connected directly or indirectly through a series of such connections.
Your task is to determine the size of the largest connected component.
Example:
For points: (1, 2), (1, 3), (2, 3), (4, 5), (5, 5), the largest connected component has size 3, since the first three points are connected together.
inputFormat
The input is read from standard input (stdin) and has the following format:
n x1 y1 x2 y2 ... xn yn
Here, n
(1 ≤ n ≤ 10^5, for example) denotes the number of points, and each of the next n
lines contains two integers representing the coordinates of a point. All points are distinct.
outputFormat
Output to standard output (stdout) a single integer: the size of the largest connected component.
## sample5
1 2
1 3
2 3
4 5
5 5
3