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