Python 노트: 그리고 집합 (DSU) 구조 안내
1. 집합 이 무엇 인지 알 아 본다.
디 스 조 인 트 세트 유 니 온 (Disjoint Set Union) 은 서로 교차 하지 않 는 집합 간 통합 과 검색 기능 을 처리 하 는 트 리 구조 로 이에 대응 하 는 결합 - 검색 알고리즘 (Union Find Algorithm) 에 맞 춰 교차 하지 않 는 집합 간 통합 과 검색 기능 의 시간 복잡 도 를 O (l o g N) O (logN) O (logN) O (logN) 는 물론 O (1) O (1) O (1) O (1) O (1) 로 대폭 줄 일 수 있다.
2. 집합 원리
그리고 집합 을 조사 하 는 핵심 사상 은 모든 상호 관련 된 집합 을 하나의 대표 요소 로 표징 하 는 것 이다. 그러면 두 요소 가 대응 하 는 대표 요 소 를 찾 아 일치 하 는 지 판단 하면 그들 이 같은 집합 에 속 하 는 지 여 부 를 판단 할 수 있다.마찬가지 로 서로 교차 하지 않 는 두 개의 집합 이 필요 하 다 면 그 중의 한 대표 요 소 를 다른 대표 요 소 를 가리 키 고 그들 로 하여 금 같은 대표 요 소 를 사용 하 게 하면 된다.
더 상세 한 원리 설명 은 아래 의 참고 링크 3 에서 칼럼 의 설명 을 참고 할 수 있 습 니 다. 그 는 수집 원리 에 대한 설명 을 매우 상세 하 게 했 습 니 다. 저 는 주로 이 칼럼 을 통 해 관련 내용 을 배우 고 수집 하 는 것 입 니 다.
3. 집합 코드 구현
1. 일반 코드 구현
다음은 일반적인 검색 집합 을 위 한 간단 한 코드 를 드 리 겠 습 니 다.
class DSU:
def __init__(self, N):
self.root = [i for i in range(N)]
def find(self, k):
if self.root[k] == k:
return k
return self.find(self.root[k])
def union(self, a, b):
x = self.find(a)
y = self.find(b)
if x != y:
self.root[y] = x
return
상기 코드 는 가장 일반적인 집합 구조 이다.
2. 최 적 화 된 DSU 구조
그러나 일반적으로 알고리즘 효율 을 높이 기 위해 우 리 는 작은 trick 를 추가 하기 도 한다.예 를 들 면:
1. 트 리 구조 조정
알고리즘 의 효율 을 더욱 잘 최적화 하기 위해 우 리 는 나무 구 조 를 제어 하여 가능 한 한 평면 화 시 켜 체인 구조 가 나타 나 깊이 가 너무 깊 지 않도록 할 수 있다. 우 리 는 나무의 깊이 를 기록 하 는 방식 으로 나무 구 조 를 최적화 시 켜 알고리즘 효율 을 최적화 시킨다.
class DSU:
def __init__(self, N):
self.root = [i for i in range(N)]
self.depth = [1 for i in range(N)]
def find(self, k):
if self.root[k] == k:
return k
return self.find(self.root[k])
def union(self, a, b):
x = self.find(a)
y = self.find(b)
xh = self.depth[x]
yh = self.depth[y]
if x == y:
return
if xh >= yh:
self.root[y] = x
self.depth[x] = max(self.depth[x], self.depth[y]+1)
else:
self.root[x] = y
2. 찾 을 때마다 노드 정보 업데이트
다른 상용 trick 는:
class DSU:
def __init__(self, N):
self.root = [i for i in range(N)]
def find(self, k):
if self.root[k] == k:
return k
self.root[k] = self.find(self.root[k])
return self.root[k]
def union(self, a, b):
x = self.find(a)
y = self.find(b)
if x != y:
self.root[y] = x
return
4. Leetcode 예제 분석
다음은 leetcode 의 예 제 를 통 해 구조의 실제 용법 을 고찰 하고 찾 아 보 겠 습 니 다.
1. Leetcode 547. Friend Circles
이 문 제 는 가장 전형 적 인 것 이 고 집합 사용 장면 을 조사 하 는 것 이다. 우 리 는 직접 조합 구 조 를 사용 하면 이 문 제 를 풀 수 있다.
직접 코드 를 제시 하여 다음 과 같이 실현 합 니 다.
class DSU:
def __init__(self, N):
self.root = [i for i in range(N)]
def find(self, k):
if self.root[k] == k:
return k
return self.find(self.root[k])
def union(self, a, b):
x = self.find(a)
y = self.find(b)
if x != y:
self.root[y] = x
return
class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
n = len(M)
dsu = DSU(n)
for i in range(n):
for j in range(i+1, n):
if M[i][j] == 1:
dsu.union(i, j)
group = set()
for i in range(n):
group.add(dsu.find(i))
return len(group)
2. Leetcode 721. Accounts Merge
이 문 제 는 위의 문제 에 비해 다소 복잡 해 보이 지만 비교적 뚜렷 한 DSU 구조 입 니 다. 우 리 는 숫자 가 아니 라 account 에 따라 dsu 관 계 를 구축 한 다음 에 서로 다른 대표 account 에 따라 해당 하 는 계 정 소유 자 를 찾 으 면 됩 니 다.
코드 를 제시 하여 다음 과 같이 실현 합 니 다.
class DSU:
def __init__(self):
self.dsu = {
}
def find(self, account):
if account not in self.dsu:
self.dsu[account] = account
return account
if account == self.dsu[account]:
return account
self.dsu[account] = self.find(self.dsu[account])
return self.dsu[account]
def union(self, x, y):
a1 = self.find(x)
a2 = self.find(y)
self.dsu[a2] = a1
return
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
mapping = {
}
dsu = DSU()
for it in accounts:
name = it[0]
key_account = it[1]
mapping[key_account] = name
for account in it[2:]:
mapping[account] = name
dsu.union(key_account, account)
res = defaultdict(list)
for account in mapping:
key_account = dsu.find(account)
res[key_account].append(account)
ans = [[mapping[k]] + sorted(v) for k, v in res.items()]
return ans
3. Leetcode 128. Longest Consecutive Sequence
이 문제 의 DSU 구 조 는 비교적 뚜렷 하 다. 바로 배열 의 모든 요소 n 을 대상 으로 n - 1 과 n + 1 도 dsu 에 나타 나 는 지 확인 하 는 것 이다. 만약 에 있 으 면 이 몇 가지 요 소 를 연결 하고 반대로 연결 하지 않 는 다.
유일 하 게 주의해 야 할 것 은 이 문제 가 집행 효율 에 대한 요구 가 비교적 높 기 때문에 우 리 는 dsu 의 나무 모양 구 조 를 최적화 시 켜 가능 한 한 평면 화 시 켜 야 한 다 는 것 이다.
다음 과 같은 코드 를 제공 합 니 다.
class DSU:
def __init__(self):
self.dsu = {
}
def find(self, n):
if n not in self.dsu:
return None
if n == self.dsu[n]:
return n
self.dsu[n] = self.find(self.dsu[n])
return self.dsu[n]
def union(self, x, y):
xr = self.find(x)
yr = self.find(y)
if xr is None or yr is None:
return
self.dsu[yr] = xr
return
def add(self, n):
if n not in self.dsu:
self.dsu[n] = n
return
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if nums == []:
return 0
dsu = DSU()
nums = list(set(nums))
for n in nums:
dsu.add(n)
dsu.union(n, n-1)
dsu.union(n, n+1)
counter = defaultdict(int)
for n in nums:
counter[dsu.find(n)] += 1
return max(counter.values())
4. Leetcode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
이 문 제 는 leetcode Weekly Contest 205 의 마지막 문제 로 당시 풀 지 못 했 으 나 지금 은 DSU 구 조 를 대충 배 운 뒤 다시 살 펴 보 자.
주체 의 사상 은 그 당시 와 일치 합 니 다. 특정한 변 으로 연 결 된 두 점 이 같은 집합 에 속 했 을 때 우 리 는 이 변 을 버 리 고 반대로 이 변 을 보존 합 니 다. 마지막 으로 하나의 전체 연결 도 를 구성 할 수 있 는 지, 할 수 있다 면 모두 몇 개의 변 을 삭 제 했 습 니 다.
DSU 구 조 를 통 해 우 리 는 이 문 제 를 신속하게 해결 하고 우리 가 실현 한 python 코드 를 다음 과 같이 제시 했다.
from copy import deepcopy
class DSU:
def __init__(self, n):
self.dsu = [i for i in range(n+1)]
def find(self, x):
if x == self.dsu[x]:
return x
self.dsu[x] = self.find(self.dsu[x])
return self.dsu[x]
def union(self, x, y):
xr = self.find(x)
yr = self.find(y)
self.dsu[yr] = xr
return
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
alice = []
bob = []
both = []
for t, x, y in edges:
if t == 1:
alice.append((x, y))
elif t == 2:
bob.append((x, y))
else:
both.append((x, y))
dsu = DSU(n)
counter3 = 0
for x, y in both:
if dsu.find(x) == dsu.find(y):
continue
dsu.union(x, y)
counter3 += 1
dsu1 = deepcopy(dsu)
counter1 = 0
for x, y in alice:
if dsu1.find(x) == dsu1.find(y):
continue
dsu1.union(x, y)
counter1 += 1
dsu2 = deepcopy(dsu)
counter2 = 0
for x, y in bob:
if dsu2.find(x) == dsu2.find(y):
continue
dsu2.union(x, y)
counter2 += 1
if counter1 + counter3 != n-1 or counter2 + counter3 != n-1:
return -1
else:
return len(edges) + counter3 - 2*n +2
5. 링크 참조
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python 노트: 그리고 집합 (DSU) 구조 안내디 스 조 인 트 세트 유 니 온 (Disjoint Set Union) 은 서로 교차 하지 않 는 집합 간 통합 과 검색 기능 을 처리 하 는 트 리 구조 로 이에 대응 하 는 결합 - 검색 알고리즘 (Union F...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
