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 -- http://mail.python.org/mailman/listinfo/python-list
