Union Find Review (Part 1)

What does Union-find track?

It tracks which items are connected and models groups that merge over time.

What are the 3 best use-cases for Union-find?

• Modeling Networks

• Clustering

• Spreading information

What does find(x) do?

It returns the root of an element, x.

What does union(A,B) do?

Merges the set containing element A with the set containing element B.

What's the difference between Fast find and Fast union?

Fast find directly connects every element in a group to its root while Fast union merges 2 groups together to create a “super-group”.

How fast/slow is union() and find() in Fast Find?

find() is fast and union() is slow because it scans everything.

How fast/slow is union() and find() in Union Find?

find() is slow because it needs to trace the root and union() is fast.

What do “Nodes” represent in Union-find?

The people or devices.

What do “interactions” represent in Union-find?

Every time you merge groups using union().

Is it true that once one member of a group is updated, the entire component is considered updated?

Yes, this is possible through Union-find.

Does union-find tell you the order or speed of which an update spreads?

No, it only tells you the connections.

What are the 3 main limitations of Union-find?

• Every connection is the same, neither one has any significance over others.

• There’s no way to separate groups after they’ve merged.

• It only tells you if elements are connected or not.

What is the efficiency (aka time complexity) of Fast-find for find and union?

• O(1) finds

• O(n) unions.

What is the worst case efficiency (aka time complexity) of Fast-union for find and union?

Both finds and unions are O(n)

What is the best case efficiency (aka time complexity) of Fast-union for find and union?

Both finds and unions are O(log n)

Can you interpret a data[] array (for either implementation) and understand the number and membership of the groups?

Yes, in fast find, Group IDs with the same data[] values are part of the same group.

In Fast union, you need to trace Group IDs to its root using data[] values, but both implementations still give you groups.