It sounds to me like you have a somewhat odd representation of an

undirected graph and you want to find connected components.

http://www.cs.sunysb.edu/~algorith/files/dfs-bfs.shtml
http://www.csee.usf.edu/~maurer/graphs/sld024.htm
etc

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

visit.extend(vs)

all_components.append(component)

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]:

neighbors[v1].add(v2)

neighbors[v2].add(v1)

Jeff

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA9wsdJd01MZaTXX0RAlLiAJ0W0EAqyLnZMffTsenA0/SDkIpivwCff0FN

TLB2hvR3Xb+bvhUWTMKHrMw=

=WNp+

-----END PGP SIGNATURE-----