Итак, вот что я хочу сделать: у меня есть список, который содержит несколько отношений эквивалентности:

l = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]

И я хочу объединить множества, которые разделяют один элемент. Вот пример реализации:

def union(lis):
  lis = [set(e) for e in lis]
  res = []
  while True:
    for i in range(len(lis)):
      a = lis[i]
      if res == []:
        res.append(a)
      else:
        pointer = 0 
        while pointer < len(res):
          if a & res[pointer] != set([]) :
            res[pointer] = res[pointer].union(a)
            break
          pointer +=1
        if pointer == len(res):
          res.append(a)
     if res == lis:
      break
    lis,res = res,[]
  return res

И это печатает

[set([1, 2, 3, 6, 7]), set([4, 5])]

Это правильно, но слишком медленно, когда отношения эквивалентности слишком велики. Я посмотрел описания алгоритма объединения-поиска:http://en.wikipedia.org/wiki/Disjoint-set_data_structure но у меня все еще есть проблема кодирования реализации Python.