擅长:python、mysql、java
<p>这是<a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow noreferrer">union-find algorithm / disjoint set data structure</a>的典型用例。在Python库AFAIK中没有实现,但是我总是倾向于在附近有一个实现,因为它非常有用。。。你知道吗</p>
<pre><code>l = [[1, 5], [5, 7], [4, 9], [7, 9], [50, 90], [100, 200], [90, 100],
[2, 90], [7, 50], [9, 21], [5, 10], [8, 17], [11, 15], [3, 11]]
from collections import defaultdict
leaders = defaultdict(lambda: None)
def find(x):
l = leaders[x]
if l is not None:
leaders[x] = find(l)
return leaders[x]
return x
# union all elements that transitively belong together
for a, b in l:
leaders[find(a)] = find(b)
# get groups of elements with the same leader
groups = defaultdict(set)
for x in leaders:
groups[find(x)].add(x)
print(*groups.values())
# {1, 2, 4, 5, 100, 7, 200, 9, 10, 50, 21, 90} {8, 17} {3, 11, 15}
</code></pre>
<p>对于n个节点,这种方法的运行时复杂度应该是O(nlogn),每次都需要logn步骤才能到达(并更新)leader。你知道吗</p>