集合并查找算法

我有数千行 1 到 100 个数字，每行定义一组数字以及它们之间的关系。 我需要获取相关数字的集合。

小例子： 如果我有这7行数据

T1 T2
T3 
T4
T5
T6 T1
T5 T4
T3 T4 T7

我需要一个不太慢的算法来知道这里的集合是：

T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5)
T3 T4 T5 T7 (because T5 is with T4 in line 6 and T3 is with T4 and T7 in line 7)

但是当你有非常大的集合时，在每个大集合中搜索 T(x) 以及进行集合的并集......等等，速度会非常慢。

您是否有提示以不那么暴力的方式做到这一点？

我正在尝试用Python 来做到这一点。

一旦构建了数据结构，您到底想要对其运行哪些查询？向我们展示您现有的代码。什么是 T(x)？您谈论“数字组”，但您的样本数据显示 T1、T2 等；请解释。

你读过这篇文章吗：http://en.wikipedia.org/wiki/Disjoint-set_data_struct http://en.wikipedia.org/wiki/Disjoint-set_data_structure

尝试看看这个 Python 实现：http://code.activestate.com/recipes/215912-union-find-data-struct/ http://code.activestate.com/recipes/215912-union-find-data-structure/

或者你可以自己提出一些相当简单易懂的东西，例如

[更新：全新代码]

class DisjointSet(object):

    def __init__(self):
        self.leader = {} # maps a member to the group's leader
        self.group = {} # maps a group leader to the group (which is a set)

    def add(self, a, b):
        leadera = self.leader.get(a)
        leaderb = self.leader.get(b)
        if leadera is not None:
            if leaderb is not None:
                if leadera == leaderb: return # nothing to do
                groupa = self.group[leadera]
                groupb = self.group[leaderb]
                if len(groupa) < len(groupb):
                    a, leadera, groupa, b, leaderb, groupb = b, leaderb, groupb, a, leadera, groupa
                groupa |= groupb
                del self.group[leaderb]
                for k in groupb:
                    self.leader[k] = leadera
            else:
                self.group[leadera].add(b)
                self.leader[b] = leadera
        else:
            if leaderb is not None:
                self.group[leaderb].add(a)
                self.leader[a] = leaderb
            else:
                self.leader[a] = self.leader[b] = a
                self.group[a] = set([a, b])

data = """T1 T2
T3 T4
T5 T1
T3 T6
T7 T8
T3 T7
T9 TA
T1 T9"""
# data is chosen to demonstrate each of 5 paths in the code
from pprint import pprint as pp
ds = DisjointSet()
for line in data.splitlines():
    x, y = line.split()
    ds.add(x, y)
    print
    print x, y
    pp(ds.leader)
    pp(ds.group)

这是最后一步的输出：

T1 T9
{'T1': 'T1',
 'T2': 'T1',
 'T3': 'T3',
 'T4': 'T3',
 'T5': 'T1',
 'T6': 'T3',
 'T7': 'T3',
 'T8': 'T3',
 'T9': 'T1',
 'TA': 'T1'}
{'T1': set(['T1', 'T2', 'T5', 'T9', 'TA']),
 'T3': set(['T3', 'T4', 'T6', 'T7', 'T8'])}