Union-Find (DSU) - Classic Problems | Repovive

CLS21. Union-Find (DSU)

1s256 MB

Implement a Union-Find (Disjoint Set Union) data structure that supports the following operations on $n$ elements (numbered 1 to $n$ ):

Initially, each element is in its own set.

\begin{array}{l} n \quad q \\ op_1 \\ op_2 \\ \vdots \\ op_q \end{array}

op_j \in \left\{ \begin{array}{ll} \texttt{UNION} \quad u \quad v \\ \texttt{FIND} \quad u \quad v \end{array} \right.

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \end{array} \quad ans_i \in \{\texttt{YES}, \texttt{NO}\}

Input

5 7
FIND 1 2
UNION 1 2
FIND 1 2
UNION 2 3
FIND 1 3
FIND 1 4
UNION 4 5

Explanation

For this input, the required output is NO YES YES NO.

Output

NO
YES
YES
NO

Input

3 4
UNION 1 2
UNION 2 3
FIND 1 3
FIND 1 2

Explanation

For this input, the required output is YES YES.

Output

YES
YES

Input

4 4
FIND 1 2
FIND 2 3
FIND 3 4
FIND 1 4

Explanation

For this input, the required output is NO NO NO NO.

Output

NO
NO
NO
NO

1s256 MB

Implement a Union-Find (Disjoint Set Union) data structure that supports the following operations on $n$ elements (numbered 1 to $n$ ):

Initially, each element is in its own set.

\begin{array}{l} n \quad q \\ op_1 \\ op_2 \\ \vdots \\ op_q \end{array}

op_j \in \left\{ \begin{array}{ll} \texttt{UNION} \quad u \quad v \\ \texttt{FIND} \quad u \quad v \end{array} \right.

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \end{array} \quad ans_i \in \{\texttt{YES}, \texttt{NO}\}

Input

5 7
FIND 1 2
UNION 1 2
FIND 1 2
UNION 2 3
FIND 1 3
FIND 1 4
UNION 4 5

Explanation

For this input, the required output is NO YES YES NO.

Output

NO
YES
YES
NO

Input

3 4
UNION 1 2
UNION 2 3
FIND 1 3
FIND 1 2

Explanation

For this input, the required output is YES YES.

Output

YES
YES

Input

4 4
FIND 1 2
FIND 2 3
FIND 3 4
FIND 1 4

Explanation

For this input, the required output is NO NO NO NO.

Output

NO
NO
NO
NO