University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

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.

bulletSan Jose set: San Jose, Los Gatos, Saratoga, Santa Clara
bulletSanta Cruz set: Santa Cruz, Capitola, Aptos
bulletMonterey set: Monterey, Pacific Grove, Carmel

What do you do with those?

Operations:

bulletMakeSet(x) - Make a new set containing element x, x becomes the representative of the set.
bulletUnion(x,y) - unites the sets that contains element x with the set that contains element y.
bulletFindSet(y) - finds the representative of the set containing y.

Applications:

bulletConnectedComponents - Creates disjoint sets with elements of a graph;
bulletSameComponent(u,v) - Determines if elements u and v belong to the same set.

 

Data Structures for Representing Disjoint Sets

bulletHow would you do it?
bulletWhat I would do if I were in your place...
bulletMore advanced techniques
bulletAnalysis