A linear-time algorithm for a special case of disjoint set union

This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a "union tree") is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in O(m+n) time and O(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in O(mα(m+n, n)+n) time and O(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving several other problems, including two-processor scheduling, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining the fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings in nonbipartite graphs.