exercise: partition a list by equivalence

[bearophileHUGS at lycos.com]

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)?

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).
Bye,
Bearophile