을 감안할 때 그룹, 개별 세트

Question

을 만들 관련 목록을 병합

감안할 때 :

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

출력 :

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

설명 : 나는 형편없는 알고리즘을 작성했습니다

(1,2) 
(1,2), (3,4) 
(1,2), (3,4), (5,6) 
(1,2), (3,4,7), (5,6) 
(1,2), (3,4,7,5,6) 

:

Case 1: both numbers in pair are new (never seen before): 
    Make a new set with these two numbers 
Case 2: one of the number in pair is new, other is already a part of some set: 
    Merge the new number in other's set 
Case 3: both the numbers belong to some set: 
    Union the second set into first. Destroy the second set. 

이 알고리즘에 대한 좀 더 공상적인 해결책이 있습니까?

Answer 1

이 경우 Unionfind algorithm을 사용할 수 있습니다. 첫째, 우리는 쌍에서 나무를 생성하기 위해 사전을 사용하고 있습니다 :

leaders = collections.defaultdict(lambda: None) 

이제 우리는 두 가지 기능 사용 - union 및 find을 - 그 나무 채우는 :

def find(x): 
    l = leaders[x] 
    if l is not None: 
     l = find(l) 
     leaders[x] = l 
     return l 
    return x 

def union(x, y): 
    lx, ly = find(x), find(y) 
    if lx != ly: 
     leaders[lx] = ly 

그냥 온통 반복을 그 쌍을 나무에 넣으십시오.

for a, b in [(1,2),(3,4),(5,6),(3,7),(5,7)]: 
    union(a, b) 

그것은 다음과 같습니다 {1: 2, 2: None, 3: 4, 4: 7, 5: 6, 6: 7, 7: None}

을 마지막으로 find에 의해 반환되는 우리 그룹 각각의 "지도자"에 의해 숫자, 즉 :

groups = collections.defaultdict(set) 
for x in leaders: 
    groups[find(x)].add(x) 

자, groups.values()은 [set([1, 2]), set([3, 4, 5, 6, 7])]

복잡도는 O (nlogn)의 순서 여야합니다.