Disjoint Set Union Problem

Disjoint Set Union Problem — ExecCode Medium DSA Practice

Solve the Disjoint Set Union problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Start with n singleton sets. Process operations union(a,b) and find(x) using path compression and union by rank. After the given ops, return the number of remaining components.

Examples

Input n = 7, ops = "[union(0,1), union(2,3), union(1,2), find(3), union(4,5), union(4,6), find(6), union(0,3)]"; Output 2. Input n = 5, ops = "[union(0,1), union(3,4), union(1,4), find(0)]"; Output 2

Constraints

1 ≤ n ≤ 10^5 Ops include union and find Nearly O(α(n)) per op amortized

Practice Disjoint Set Union free on ExecCode. Browse DSA problems, topic map, and placement guides.