clever programming solution wanted

Jeff Epler jepler at
Fri Jul 16 00:54:21 CEST 2004

It sounds to me like you have a somewhat odd representation of an
undirected graph and you want to find connected components.

In an edge-list representation, I think the solution looks something
like (untested):
    all_components = []
    while input:
        initial_element = input.pop()
        visit = [initial_element]
        component = Set([initial_element])
        while visit:
            v = visit.pop()
            vs = neighbors[v] - component:
            component |= vs
        input -= component
This is a O(V+E) algorithm unless I messed something up.

Converting from your d[Ki] = [Tj, Tk, ...] to edge-list representation
is probably O(V^2).  Something like (untested):
    neighbors = dict([(v, Set()) for v in d])
    ds = dict([(k, Set(v)) for k, v in d.iteritems()])
    for v1 in d:
        for v2 in d:
            if ds[v1] & ds[v2]:

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <>

More information about the Python-list mailing list