University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

What I would do if I was in your place

I could start with a list:

This represents 10 sets with one element each

Index Element Representative
0 San Jose San Jose
1 Los Gatos Los Gatos
2 Santa Clara Santa Clara
3 Saratoga Saratoga
4 Capitola Capitola
5 Santa Cruz Santa Cruz
6 Monterey Monterey
7 Carmel Carmel
8 Aptos Aptos
9 Pacific Grove Pacific Grove

and I could promote the appropriate Unions:

Index Element Representative
0 San Jose San Jose
1 Los Gatos San Jose
2 Santa Clara San Jose
3 Saratoga San Jose
4 Capitola Santa Cruz
5 Santa Cruz Santa Cruz
6 Monterey Monterey
7 Carmel Monterey
8 Aptos Santa Cruz
9 Pacific Grove Monterey

But, in fact, I would like to do a little better:

set an index to locate the position of the representative (I could have used a pointer as well ...)

Index Element Representative
0 San Jose 0
1 Los Gatos 0
2 Santa Clara 0
3 Saratoga 0
4 Capitola 5
5 Santa Cruz 5
6 Monterey 6
7 Carmel 6
8 Aptos 5
9 Pacific Grove 6

Another alternative:

Each element points to another element in the same set. Representative points to itself.

Index Element Next in set
0 San Jose 0
1 Los Gatos 2
2 Santa Clara 3
3 Saratoga 0
4 Capitola 5
5 Santa Cruz 5
6 Monterey 6
7 Carmel 6
8 Aptos 4
9 Pacific Grove 7

Or, you could have a combination... points to next and to representative.

Complexity:

Operation index to representative index to next
MakeSet O(1) O(1)
FindSet O(1) O(n)
Union O(m) O(m)