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.