数据结构（七）：并查集
约 227 字
预计阅读 1 分钟
次阅读
- 并查集（Union Find）也叫「不相交集合（Disjoint Set）」，是一种树型的数据结构，专门用于 动态处理 不相交集合的「查询」与「合并」问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class DSU:
def __init__(self,n):
self.f = list(range(n))
self.sz = [1]*n
self.cc = n
def find(self,x):
if self.f[x]!=x:
self.f[x] = self.find(self.f[x])
return self.f[x]
def union(self,x,y):
f,sz = self.f,self.sz
fx,fy = self.find(x),self.find(y)
if fx==fy:
return False
if sz[fx]>sz[fy]:
fx,fy = fy,fx
f[fx] = fy
sz[fy] += sz[fx]
self.cc -= 1
return True
|
例题