Union-Find

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/e0TJP/implementing-kruskals-algorithm-via-union-find-i
• https://www.coursera.org/learn/algorithms-greedy/lecture/TvDMg/implementing-kruskals-algorithm-via-union-find-ii
• https://www.coursera.org/learn/algorithms-greedy/lecture/WX3tg/lazy-unions-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/RF7aH/union-by-rank-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/r2nA3/analysis-of-union-by-rank-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/Rhh6y/path-compression-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/KdbbU/path-compression-the-hopcroft-ullman-analysis-i-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/ttbcu/path-compression-the-hopcroft-ullman-analysis-ii-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/KZvAe/the-ackermann-function-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/RqR0G/path-compression-tarjans-analysis-i-advanced-optional
• https://www.coursera.org/learn/algorithms-greedy/lecture/aqa6f/path-compression-tarjans-analysis-ii-advanced-optional

Internal

• Data Structures
• Kruskal's Algorithm

Canonical Use

The canonical use of a union-find data structure is to maintain a partition of a set of objects. Examples:

• Maintaining the connected components that represent partial spanning trees in Kruskal's algorithm.

Supported Operations

FIND(X)

Given an object from the universe of objects maintained by the union-find, return the name of the group (partition) this object belongs.

UNION(C_i,C_j)

The union operation takes the name of two groups and fuses the groups together: the objects in group C_i and the objects in group C_j coalesced and become members of a sole group.