← 返回 uber 的题目列表Minimum Triggers to Absorb All Balls (Connected Components by Row/Column Within Distance)
类型:online_judge
You are given n balls on a 2D plane with coordinates (x[i], y[i]). Two balls are directly connected if and only if either:
they share the same row (same y) and |x1 - x2| <= d, or
they share the same column (same x) and |y1 - y2| <= d.
Connectivity is transitive: balls in the same connected component will be absorbed together.
In one trigger, you may pick any not-yet-absorbed ball; then the entire connected component containing it gets absorbed. Find the minimum number of triggers needed to absorb all balls.
Input:
n, d
n lines of x[i], y[i]
Output:
minimum triggers (number of connected components).
Example
Input
1 3
0 0
Output
1