exercise: partition a list by equivalence

[David Eppstein]

In article <eppstein-8851A4.18394418022005 at news.service.uci.edu>,
 David Eppstein <eppstein at ics.uci.edu> wrote:

> It can be solved by union-find
> (e.g. with UnionFind from <http://www.ics.uci.edu/~eppstein/PADS/>):

Here's a cleaned up version, after I added a proper iter() method to the 
UnionFind data structure:

import UnionFind

def merge(pairs):
    uf = UnionFind.UnionFind()
    for a,b in pairs:
        uf.union(a,b)
    components = {}
    for a in uf:
        components.setdefault(uf[a],[]).append(a)
    return components.values()

> If you do all the unions before all the finds, as in this algorithm, 
> union-find is O(n).

That was a little too sloppy.  It is possible to solve the union find 
problem, with all unions before all finds, in time O(n).  However the 
usual union find data structure takes more time, O(n alpha(n)).

> However it might be easier to treat the input pairs as the edges of a 
> graph and apply a depth-first-search based graph connected components 
> algorithm.

This would be O(n), though.

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/