|
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) |
|