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

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 algorighm for the general problem, which runs in \(O(m\alpha (m+n,n)+n)\) time and O(n) space, where \(\alpha\) is a functional inverse of Ackermann's function.