Today we often face a certain kind of problem called dynamic connectivity:
Given a set of N objects.
- Union command: connect two objects.
- Find/connected query: is there a path connecting the two objects?
So there are 2 types of operation in this:
- Find query. Check if two objects are in the same component.
- Union command. Replace components containing two objects with their union.