exercise: partition a list by equivalence

[David Eppstein]

In article <1108837453.883740.309270 at f14g2000cwb.googlegroups.com>,
 bearophileHUGS at lycos.com wrote:

> David Eppstein:
> > 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.
> 
> Is the DFS the best one here (instead of BFS)?

I'm not sure it makes much difference.

> With the graph implementation that I've just shown here it becomes:
> 
> . import graph
> . def merge(l):
> .     g = graph.Graph()
> .     g.addArcs(l)
> .     return g.connectedComponents()
> . print merge( [ [1,2], [2,4], [5,6] ] )
> 
> I presume the complexity is O(n+a); n (the nodes) is proportional to
> the number of pairs, and
> a (the arcs) depends on the "intricacy" of the input pairs. For a
> complete graph, this can
> become slow (but there is a high probably that all the pairs are in the
> same connected component).

It's still linear in the input size, which is the best you could hope 
for.

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