Arnaud Delobelle wrote:
> I think I would go for the two-step approach of constructing the graph
> first and then recursively building connected components. It sounds
> more complicated at first but when you implement it it turns out quite
> simple:
>
> from collections import defaultdict
> from itertools import count
>
> def build_groups(edges):
> neighbors = defaultdict(set)
> for x, y in edges:
> neighbors[x].add(y)
> neighbors[y].add(x)
>
> groups, group_indices = {}, count(1)
> def set_group(x, group_index):
> groups[x] = group_index
> for y in neighbors[x]:
> if y not in groups:
> set_group(y, group_index)
>
> for x in neighbors:
> if x not in groups:
> set_group(x, group_indices.next())
> return groups
That looks a little less like legwork than mine. My only objection is that
you may hit Python's low recursion limit.
Peter
--
http://mail.python.org/mailman/listinfo/python-list
