Take quiz & check grades
Disjoint Sets
What are?
Sets of elements so that one element does not belong to more than one set.
Ex.
 | San Jose set: San Jose, Los Gatos, Saratoga, Santa Clara |
| Santa Cruz set: Santa Cruz, Capitola, Aptos |
| Monterey set: Monterey, Pacific Grove, Carmel |
What do you do with those?
Operations:
| MakeSet(x) - Make a new set containing element x, x becomes the representative of the set. |
| Union(x,y) - unites the sets that contains element x with the set that contains element y. |
| FindSet(y) - finds the representative of the set containing y. |
Applications:
| ConnectedComponents - Creates disjoint sets with elements of a graph; |
| SameComponent(u,v) - Determines if elements u and v belong to the same set. |
Data Structures for Representing Disjoint Sets
| How would you do it? |
| What I would do if I were in your place... |
| More advanced techniques |
| Analysis |