PROBLEM LINKS
DIFFICULTY
MEDIUM
PREREQUISITES
DISJOINT SETS
PROBLEM
For each query of type 0, connect the two sets containing the given numbers and for each query of type 1 find if the given numbers are in the same set.
EXPLANATION
This can be done using disjoint set forests and heuristics to improve running time. Reepresent sets by rooted trees, with
each node containing one member and each tree representing one set. Here we can use 2 heuristics.
The first heuristic, union by rank is to make the root of the tree with fewer nodes point to the root of the tree with more nodes.
Rather than explicitly keeping track of the size of the subtree rooted at each node, we shall use an approach that eases the analysis. For each node, we maintain a rank, which is an upper bound on the height of the node. In union by rank, we
make the root with smaller rank point to the root with larger rank during a UNION operation.
The second heuristic, path compression, is also quite simple and highly effective. We use it to check if two nodes are in the same set. Here we use a parent pointer for each node. And while going up to the root from the current node, we point the node directly to the root making it easy (in time) when you check with a new node next time.