Disjoint Set Union

Practice this coding question on Coding Gurukul.

Problem statement

Implement Disjoint Set Union for n elements numbered 0 to n-1. Initially, each element is in its own set. - UNION u v: merge the sets containing u and v. - SAME u v: print YES if u and v are in the same set, otherwise NO. - COUNT: print the number of sets. Merging elements already in the same set changes nothing. UNION produces no output. Use path compression and union by size or rank. Worked example UNION 0 1 and UNION 1 2 put 0, 1 and 2 in one set. SAME 0 2 prints YES; SAME 0 3 prints NO. Two sets remain, so COUNT prints 2.

Input format

First line: n q. Next q lines: UNION u v, SAME u v, or COUNT.

Output format

One line for each SAME or COUNT.

Constraints

1 <= n,q <= 100000; 0 <= u,v < n. At least one output command.

Sample input

4 5
UNION 0 1
UNION 1 2
SAME 0 2
SAME 0 3
COUNT

Sample output

YES
NO
2

Sign in to run or submit a solution in C++, Java or Python.