2010م - 1444هـ
Worst Case



Introduction

A well-known problem in data structures is the set union problem, defined as

follows: Carry out a sequence of intermixed operations of the following three kinds

on labeled sets:

make set(e, l): Create a new set with label l containing the single element e. This

operation requires that e initially be in no set.

find label(e): Return the label of the set containing element e.

unite(e, f): Combine the sets containing elements e and finto a single set, whose

label is the label of the old set containing element e. This operation requires that

elements e andfinitially be in different sets.

Because of the constraint on make set, the sets existing at any time are disjoint

and define a partition of the dements into equivalence classes. For this reason the

set union problem has been called the equivalence problem by some authors. A

solution to the set union problem can be used in the compiling of FORTRAN

Authors addre ,sses: R. E. Tarjan, AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ

07974; J. van Leeuwen, Department of Computer Science, University of Utrecht, Utrecht, The

Netherlands.