Connected Components of Rectangles

Given n rectangles on the plane, where the i^th rectangle contains all points \( (x,y) \) satisfying \( x\in [A_i, C_i] \) and \( y\in [B_i, D_i] \) (points on the boundary are included), determine the connected components of the set of rectangles.

Two rectangles are defined as adjacent if and only if there exists a point that is contained in both rectangles. Two rectangles \( a \) and \( b \) are said to be connected if there exists a sequence \( s_1, s_2, \ldots, s_k \) (with \( k\ge 1 \)) such that \( s_1=a, \ s_k=b \) and for every \( 1\le i<k \), \( s_i \) and \( s_{i+1} \) are adjacent.

A set \( S \) of rectangles forms a connected component if:

• For every \( i,j\in S \), rectangles \( i \) and \( j \) are connected.
• For every \( i\in S \) and \( j\notin S \), rectangles \( i \) and \( j \) are not connected.

Your task is to compute the connected components for the given rectangles and assign each rectangle a label indicating its connected component. The labels should be non-negative integers from \( 0 \) to \( m-1 \), where \( m \) is the total number of connected components. Rectangles in the same connected component must have the same label, and rectangles in different components must have different labels.

Note: Two rectangles \( i \) and \( j \) are considered adjacent if and only if \[ \text{not} \big( C_i < A_j \;\text{or}\; C_j < A_i \;\text{or}\; D_i < B_j \;\text{or}\; D_j < B_i \big). \]

inputFormat

You are given the following parameters as input to the function find_union:

• n: an integer representing the number of rectangles.
• A, B, C, D: four lists (or arrays) of length n of integers. The i^th rectangle covers the points \( (x,y) \) such that \( x\in [A[i], C[i]] \) and \( y\in [B[i], D[i]] \). (Note: indices in the problem statement are 0-indexed.)

The input is passed as function arguments; you are not required and should not use standard input.

outputFormat

Your function find_union should return a list (or array) of length n of non-negative integers. For any indices \( i \) and \( j \), the output values satisfy \( u[i] = u[j] \) if and only if the corresponding rectangles are in the same connected component. Valid labels are in the range \( [0, m) \) where \( m \) is the number of connected components.

The output is returned from the function; do not use standard output.

sample

n = 3
A = [0, 2, 5]
B = [0, 2, 2]
C = [3, 4, 7]
D = [3, 4, 5]

[0, 0, 1]