Introduction
Syllabus
Guidelines for labs
Lab sections
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
