In article <[EMAIL PROTECTED]>, David Eppstein <[EMAIL PROTECTED]> 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/ -- http://mail.python.org/mailman/listinfo/python-list
